排序算法——堆排序

堆排序

堆排序(Heapsort)是指利用堆这种数据结构进行的一种排序算法。堆排序的平均时间复杂度为O(nlogn)。

堆可以分为大顶堆和小顶堆

  1. 大顶堆:每个节点的值都大于或等于其子节点的值,在堆排序算法中用于升序排列。
  2. 小顶堆:每个节点的值都小于或等于其子节点的值,在堆排序算法中用于降序排列。

小顶堆

将上图小顶堆中的节点按照层次从上到下从左到右依次编号,并将节点映射到数组中即可得到下面结果

小顶堆结果映射结果

观察小顶堆树结构以及映射的数组结果,可以得到以下公式:

1
小顶堆: arr[i] <= arr[2i + 1] && arr[i] <= arr[2i + 1]

同理,大顶堆也可以得到一个公式来描述节点关系

大顶堆

将上图小顶堆中的节点按照层次从上到下从左到右依次编号,并将节点映射到数组中即可得到下面结果

大顶堆节点映射结果

1
大顶堆: arr[i] >= arr[2i + 1] && arr[i] >= arr[2i + 1]

堆排序算法步骤

  1. 创建一个堆H[0……n-1];
  2. 把堆顶(最大值)和堆尾交换
  3. 把堆的尾索引缩小1,并重新堆化,目的是把交换到堆顶的节点放在相应的正确的位置,史整个堆树满足大(小)顶堆的特性。
  4. 重复步骤2,直到堆的尾索引为0

步骤一: 构建初始堆树,这里我们构建大顶堆,用来升序排列。

1、假如有一个无序的数列结构,如下:

无序数列结构

2、从最后一个非叶子结点开始调整(第一个非叶子结点:arr.length / 2 - 1 = 15/2-1 = 6,也就是46这个节点) ,从左到右,从下到上进行调整

从第一个非叶子结点开始调整

3、找到第二个非叶子结点65,因为在[65,31,77]中,77最大,所以这里65和77交换

调整第二个非叶子结点

4、找到第三个非叶子结点35,因为在[35,30,20]中,35最大,所以这里不做交换

调整第三个非叶子结点

5、找到第四个非叶子结点13,因为在[13,65,10]中,65最大,所以这里13和65做交换

调整第四个非叶子结点

6、找到第五个非叶子结点96,因为在[96,77,81]中,96最大,所以这里不做交换

调整第五个非叶子结点

7、找到第六个非叶子结点60,因为在[60,65,35]中,65最大,所以这里60和65做交换

调整第六个非叶子结点

8、找到第七个非叶子结点91,因为在[91,65,96]中,96最大,所以这里91和96做交换

调整第七个非叶子结点

步骤二: 将堆顶元素与末尾元素进行交换,使末尾元素最大。然后继续调整堆,再将堆顶元素与末尾元素交换,得到第二大元素。如此反复进行交换、重建、交换

1、将堆顶元素96和末尾元素22进行交换

交换堆顶和堆尾元素

2、重新调整堆树,使其继续满足堆定义

重新调整堆树,使其满足堆定义

3、重复以上步骤,可以得到最终的堆树结构如图所示

最终堆排序树结构

动态图演示

堆排序动态图1

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
public class HeapSort {
/**
* 构建大顶堆
* @param data 数据
* @param start 构建堆的开始位置
* @param end 构建堆的结束位置 防止重复建堆
*/
public static void maxTopHeap(int[] data, int start, int end) {
int parent = start;
// 下标是从0开始就加1,否则就不需要加1
int son = parent * 2 + 1;
while(son < end) {
// 比较左右节点的大小
int temp = son;
// 表示右节点比左节点大
if (son + 1 < end && data[son] < data[son + 1]) {
// 要交换父节点和右节点
temp = son + 1;
}
// 不用交换
if (data[parent] > data[temp]) {
return ;
} else {
// 交换
int tmp = data[parent];
data[parent] = data[temp];
data[temp] = tmp;
// 继续堆化
parent = temp;
son = parent * 2 + 1;
}
}
}

/**
* 堆排序
* @param data
*/
public static void heapSort(int[] data) {
int length = data.length;
/**
* i = length / 2 - 1 怎么来的?
* 在完全二叉树中,第一个非叶子结点其实就是最后一个叶子节点的父节点。
* 假设节点的索引值为i,则其左子叶索引值为2i + 1; 右子叶索引值为2i + 2;
* 因为最后一个叶子节点的索引值是n - 1,所以他的父节点索引为((n - 1) - 1) / 2 即n/2 - 1
*/
for (int i = length / 2 - 1; i >= 0 ; i--) {
maxTopHeap(data,i,length);
}
for (int i = length - 1; i > 0 ; i--) {
int temp = data[0];
data[0] = data[i];
data[i] = temp;
maxTopHeap(data,0,i);
}
}
}

  • 版权声明: 本博客所有文章除特别声明外,著作权归作者所有。转载请注明出处!

请我喝杯咖啡吧~

支付宝
微信