堆排序-笔记

算法概述

有了前一篇 优先队列与堆 的铺垫,理解堆排序就容易多了。基本思想就是由所有待排序元素构建一个可删除最大元素的堆,然后重复删除最大元素即可将它们按顺序删去。如果用无序数组实现的优先队列,这么做相当于进行一次插入排序。用基于堆的优先队列,就产生一种新的排序算法-堆排序。

算法描述与实现

显然,堆排序可以分为两个阶段:在堆的构造阶段,将原始数组重新安排组织进一个堆中;然后在下沉排序阶段,从堆中按递减顺序取出所有元素就得到最终的排序结果。

堆的构造在前一篇中已经详细讲述过,这里不再重复。不过之前的构造实现是将需要排序的数组拷贝一份,将副本用作堆,而这里的实现将需要排序的数组本身作为堆,这样就无需任何额外空间。下沉排序的工作就是将堆中最大元素(根元素)和堆尾元素交换位置,然后堆大小减一,接着下沉新的根元素以恢复堆序性(换个方式描述就是删除最大元素,然后放入堆缩小后堆尾之后空出的位置),重复此过程,直到堆缩小为一。整个排序过程和选择排序有些类似,不断选择出剩余之中最大的,但所需的比较要少得多。

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

public void sort(Comparable[] a) {
int n = a.length;

// 构造阶段
for (int k = n/2; k >= 1; k--) {
sink(a, k, n);
}

// 下沉排序阶段
while (n > 1) {
exch(a, 1, n--);
sink(a, 1, n);
}
}

private void sink(Comparable[] a, int k, int n) {
Comparable tmp = get(a, k);
int hole = k;
while (2*hole <= n) {
int child = 2*hole;
// 找到较大的儿子
if ((child+1) <= n && less(a, child, child+1)) {
child++;
}
if (less(tmp, get(a, child))) {
move(a, child, hole);
hole = child;
} else {
break;
}
}
set(a, hole, tmp);
}

protected boolean less(Comparable[] a, int i, int j) {
return less(a[i-1], a[j-1]);
}

protected void exch(Object[] a, int i, int j) {
Object t = a[i-1];
a[i-1] = a[j-1];
a[j-1] = t;
}

private Comparable get(Comparable[] a, int i) {
return a[i-1];
}

private void set(Comparable[] a, int i, Comparable v) {
a[i-1] = v;
}

private void move(Object[] a, int from, int to) {
a[to-1] = a[from-1];
}

算法性能评估

用 sink 操作由 N 个元素构造堆只需少于 2N 次比较以及少于 N 次交换。

将 N 个元素排序,堆排序只需少于 $(2NlgN+2N)$ 次比较,以及一半次数的交换。其中 2N 项来自于堆的构造。

堆排序是我们所知的唯一能够同时最优地利用时间和空间的方法——在最坏情况下它也能保证使用 ~$2NlgN$ 次比较和恒定的额外空间。因此在空间十分紧张的时候,它也有较好的性能,例如在嵌入式系统和低成本的移动设备中。但现代系统中的许多应用并不使用它,因为它无法利用缓存。数组元素很少和相邻的元素进行比较,导致缓存未命中的次数远远高于大多数比较都在相邻元素间进行的算法,如快速排序、归并排序,甚至是希尔排序。

另一个优点是它能在插入操作和删除最大/小元素操作混合的动态场景中保证对数级别的运行时间。

参考资源

《算法(第四版)》Robert Sedgewick 等著,第 2 章-排序

0%