本文参考于：八大排序算法总结与java实现
堆排序 （Head Sort）
1991年的计算机先驱奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德(Robert W．Floyd) 和威廉姆斯(J．Williams) 在1964年共同发明了著名的堆排序算法(Heap Sort).
堆的定义如下：n个元素的序列 {k1,k2,⋅⋅⋅,kn} 当且仅当满足下关系时，称之为堆。
小顶堆：{ki≤k2iki≤k2i+1大顶堆：{ki≥k2iki≥k2i+1(i=1,2,...,⌊n2⌋)小顶堆：\begin{cases}k_i \leq k_{2i}\\\\k_i \leq k_{2i+1}\end{cases}
大顶堆：\begin{cases}k_i \geq k_{2i}\\\\k_i \geq k_{2i+1}\end{cases}
(i=1,2,...,\left \lfloor \frac{n}{2} \right \rfloor)
其中的两种情况又分为小顶堆和大顶堆
把此序列对应的二维数组看成一个完全二叉树。
那么堆的含义就是：完全二叉树中任何一个非叶子节点的值均不大于（或不小于）其左，右孩子节点的值。
由上述性质可知大顶堆的堆顶的关键字肯定是所有关键字中最大的，小顶堆的堆顶的关键字是所有关键字中最小的。
因此我们可使用大顶堆进行升序排序, 使用小顶堆进行降序排序。
基本思想
先将序列建立堆，然后输出堆顶元素，然后再将剩下的序列在建立新的堆，在输出堆顶元素，以此类推，直到所有元素均输出为止，此时输出的元素序列即为有序序列
动态演示如下图所示：
算法描述
- 先将初始序列K[1…n]建成一个大顶堆, 那么此时第一个元素K1最大, 此堆为初始的无序区
- 再将关键字最大的记录K1 (即堆顶, 第一个元素)和无序区的最后一个记录 Kn 交换,并将Kn取出， 由此得到新的无序区K[1…n-1]和有序区K[n]
- 交换K1 和 Kn 后, K1在堆顶可能违反堆性质, 因此需将K[1…n-1]调整为堆. 然后重复步骤2, 直到无序区只有一个元素时停止.
简单总结可以分为三个部分操作
- 建立堆(大顶堆or小顶堆)
- 取出堆顶元素，将最后一个元素放在堆顶
- 重建堆，重复步骤2
对于堆节点的访问：
- 父节点i的左子节点在位置：
(2*i+1);
- 父节点i的右子节点在位置：
(2*i+2);
- 子节点i的父节点在位置：
floor((i-1)/2);
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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
|
public class HeadSort {
public static void main(String[] args) {
int[] arr = {49, 38, 65, 97, 26, 13, 27, 49, 55, 4};
System.out.println("排序前:" + Arrays.toString(arr));
HeadSort1(Arrays.copyOf(arr, arr.length));
HeadSort2(Arrays.copyOf(arr, arr.length));
}
private static void HeadSort2(int[] arr) {
int len = arr.length;
while (len > 0) {
buidHead(arr, len);
int temp = arr[0];
arr[0] = arr[len - 1];
arr[len - 1] = temp;
len = len - 1;
}
System.out.println("排序后:" + Arrays.toString(arr));
}
private static void buidHead(int[] arr, int len) {
for (int i = len / 2; i >= 0; i--) {
int leftIndex = 2 * i + 1;
int rightIndex = leftIndex + 1;
int maxIndex = i;
if (leftIndex < len && arr[leftIndex] > arr[maxIndex]) {
maxIndex = leftIndex;
}
if (rightIndex < len && arr[rightIndex] > arr[maxIndex]) {
maxIndex = rightIndex;
}
if (maxIndex != i) {
int temp = arr[i];
arr[i] = arr[maxIndex];
arr[maxIndex] = temp;
}
}
}
private static void HeadSort1(int[] arr) {
for (int i = arr.length; i > 0; i--) {
buildMaxHead(arr, i);
int temp = arr[0];
arr[0] = arr[i - 1];
arr[i - 1] = temp;
}
System.out.println("排序后:" + Arrays.toString(arr));
}
private static void buildMaxHead(int[] arr, int limit) {
if (arr.length <= 0 || arr.length < limit) {
return;
}
int parentIdx = limit / 2;
for (; parentIdx >= 0; parentIdx--) {
if (parentIdx * 2 + 1 >= limit) {
continue;
}
int left = parentIdx * 2 + 1;
int right = (left + 1) >= limit ? left : (left + 1);
int maxChildId = arr[left] >= arr[right] ? left : right;
if (arr[maxChildId] > arr[parentIdx]) {
int temp = arr[parentIdx];
arr[parentIdx] = arr[maxChildId];
arr[maxChildId] = temp;
}
}
}
}
|
复杂度
以上,
- 建立堆的过程, 从length/2 一直处理到0, 时间复杂度为O(n);
- 调整堆的过程是沿着堆的父子节点进行调整, 执行次数为堆的深度, 时间复杂度为O(lgn);
- 堆排序的过程由n次第2步完成, 时间复杂度为O(nlgn).
| 平均时间复杂度 |
最好情况 |
最坏情况 |
空间复杂度 |
| O(nlog2n) |
O(nlog2n) |
O(nlog2n) |
O(1) |
Tips: 由于多次任意下标相互交换位置, 相同元素之间原本相对的顺序被破坏了, 因此, 它是不稳定的排序.
适用场景
由于堆排序中初始化堆的过程比较次数较多, 因此它不太适用于小序列.
在堆排序算法分析过程中可以发现，堆排序通过构建堆，率先将最大或者最小的元素找出来。
所以，堆排序往往适用于，不需要对序列整体排序，只需要找到最大或者最小元素的场景
