理解了上篇二叉堆的知识，堆排序（heap sort）就非常简单了。
堆排序代码
（会用到上一篇中 MaxHeap 类的代码）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
private int[] heapSort(int[] data) {
int len = data.length;
MaxHeap heap = new MaxHeap(len);
for (int d : data) {
heap.insert(d);
}
for (int i = len - 1; i >= 0; i--) {
data[i] = heap.getMax();
}
return data;
}
|
堆排序优化代码
主要优化了上面代码中构建堆的方式。
上一篇说过，上面代码构建堆的时间复杂度是 O(nlogn)，我们可以把它优化到 O(n)。
（会用到上一篇中 MaxHeap 类的代码）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
private int[] heapSort(int[] data) {
int len = data.length;
MaxHeap heap = new MaxHeap(data, len);
for (int i = len - 1; i >= 0; i--) {
data[i] = heap.getMax();
}
return data;
}
|
堆排序再优化
上面两种堆排序的代码都额外使用了 O(n) 的空间来创建堆，所以空间复杂度为 O(n)。
这个结果并不能让人满意，不过恰好还有一种更优的思路，可以应用最大堆的原理直接在原数组中进行排序，不需要任何额外的空间，将空间复杂度优化为 O(1)。
具体思路是：
一个数组本身就可以看做是一个堆，首先通过 Heapify 过程将它构建成一个最大堆；（数组长度记为 n）
此时，数组中的最大值就是当前第一个元素（记为 i），当整个数组排好序后，它的正确位置应该是数组末尾。所以把它和当前数组的末尾元素（记为 j）交换位置；
由于把 j 放到了数组第一个位置，此时，数组 [0, n - 1] 索引区间不再符合最大堆的性质，所以要把这个区间调整成最大堆。很简单，只需要在这个区间中对 j 做一次 shiftDown 操作就可以了；
此时，数组 [0, n - 1] 索引区间中的最大元素又在第一个位置了，之后再像之前一样操作。以此类推，直到整个数组都排好序。
可以发现，这个思路其实就是从上一篇中的 Heapify 和 shiftDown 算法来的。
堆排序再优化代码
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
|
private int[] heapSort(int[] data) {
int len = data.length, temp;
for (int i = (len - 2) / 2; i >= 0; i--) {
shiftDown(data, len, i);
}
for (int i = len - 1; i > 0; i--) {
temp = data[0];
data[0] = data[i];
data[i] = temp;
shiftDown(data, i, 0);
}
return data;
}
private void shiftDown(int[] data, int len, int i) {
int e = data[i];
int il, ir;
while ((il = 2 * i + 1) < len) {
int j = il;
if ((ir = j + 1) < len && data[ir] > data[j]) {
j = ir;
}
if (e >= data[j]) {
break;
}
data[i] = data[j];
i = j;
}
data[i] = e;
}
|
复杂度和稳定性分析
- 时间复杂度
构建最大堆时间复杂度为 O(n)，每个元素做一次 shiftDown 操作时间复杂度为 O(logn)，所以整体的时间复杂度为 O(n * logn)。
最优时间复杂度：O(n * logn)
最坏时间复杂度：O(n * logn)
平均时间复杂度：O(n * logn)
- 空间复杂度：O(1)
- 堆排序是一种不稳定排序。