希尔排序-笔记

算法描述

对于大规模乱序数组,插入排序很慢,因为它只会交换相邻的两个元素,这样元素只能一点一点地从一端移动到另一端。虽然改进后的版本不再需要交换操作了,但是比待插入元素大或小的所有元素都要逐个向右移动一位,以便腾出一个插入位置。

希尔排序是一种基于插入排序的快速排序算法。它简单地改进了插入排序,交换不相邻的元素以对数组的局部进行排序,然后使用插入排序对局部有序的数组排序。这正展示了初级排序算法性质的价值

希尔排序的思想是每一轮排序使数组中 间隔为 $h_k$ 的每一组元素都是有序的。h 序列是一个递增序列 $h_1$, $h_2$, …, $h_t$。每轮排序从大到小取用 h 序列中的值作为间隔,那么最后一轮的间隔为 $h_1$。因此,只要 $h_1=1$,希尔排序就能够使整个数组有序。也就是说,对于任意以 1 结尾的 h 序列,它都能够将数组排序。

上文中把数组看作是由间隔为 $h_k$ 的多组元素穿插在一起组成的,虽然便于讲述希尔排序的思想,但是不够直观。换一种描述方式感觉就好多了,现在我们把数组看作由 $h_k$ 个互相独立的数组编织在一起形成的。如下图所示:

先引入一个概念,一个 h 有序 的数组就是一个由 h 个互相独立的有序数组编织在一起组成的数组(请看上图)。

每轮排序使用插入排序对这 $h_k$ 个子数组进行排序。如果 $h_k$ 很大,很轻松就可以将元素移动到很远的位置,解决了插入排序需要一点一点向前交换位置或逐个右移一位的问题。同时也为实现更小的 $h_k-1$ 有序创造了方便,换句话说就是 $h_k$ 个数组都有序会使下一轮(使 $h_k-1$ 个数组都有序)的工作相对较容易。这体现了希尔排序的一个重要性质
一个 $h_k$ 有序的数组会一直保持是 $h_k$ 有序的,即使是在下一轮排序之后。前面各轮排序的成果不会被后面的各轮排序给打乱。

实现希尔排序有一个很简单的方法,使用插入排序对 $h_k$ 个子数组进行排序时,只需要将插入排序实现代码中移动元素的步长由 1 改为 $h_k$ 即可。这样希尔排序的实现就转化为了一个类似于插入排序,但使用不同移动步长的过程。

算法实现

下面的实现使用的 h 序列为 $h_k=(3^k-1)/2$ (k=1, 2, 3, …)。当然也可以选择其他更好的递增序列。

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 void sort(Comparable[] a) {
int n = a.length;

// 3x+1 increment sequence: 1, 4, 13, 40, 121, 364, 1093, ...
int h = 1;
while (h < n/3) {
h = 3*h + 1;
}

// 每次循环就对 h 个子数组进行排序
while (h >= 1) {
// 注意, h 既是子数组的个数, 又是子数组穿插在一起形成的段的大小。
// 这一层循环应将其理解为段的大小, 通过遍历从第二段开始的所有元素
// 就可以同时对所有子数组进行排序
for (int i = h; i < n; i++) {
for (int j = i; j >= h && less(a[j], a[j-h]); j -= h) {
exch(a, j, j-h);
}
}
assert isHSorted(a, h);
h /= 3;
}
}

/**
* 检查数组是否是 h 有序的 (h-sorted)。
* 与 isHSorted2 方法等效, 实现上的区别是该方法同时检查所有子数组,
* 而 isHSorted2 方法逐个单独检查每个子数组。
*/
private boolean isHSorted(Comparable[] a, int h) {
// 这里应将 i 理解为段的大小
for (int i = h; i < a.length; i++) {
if (less(a[i], a[i-h])) {
return false;
}
}
return true;
}

/**
* 逐个单独检查每个子数组是否有序
*/
private boolean isHSorted2(Comparable[] a, int h) {
int n = a.length;
// 外层循环中应将 h 理解为子数组个数,
// 每次循环检查一个子数组是否有序。
// i 就是每个子数组第一个元素的索引
for (int i = 0; i < h; i++) {
// 内层循环中应将 h 理解为段的大小
for (int j = i; j < n; j += h) {
if (less(a[j+h], a[j])) {
return false;
}
}
}
return true;
}

为了辅助理解上面的算法实现,画了一幅简图展现 h 的两种含义:

算法性能评估

目前最重要的结论是希尔排序的运行时间突破了平方级别。但理论上来说,目前还没有人能够证明希尔排序对于随机数据的运行时间是线性对数级别的。透彻理解希尔排序的性能特征至今仍然是一项挑战。

一个影响算法性能的因素是所使用的 h 递增序列。上面的实现使用的序列很简单,性能接近于复杂递增序列。但优秀的递增序列可能会带来 20% ~ 40% 的性能提升。

与其他算法相比较

和选择、插入排序相比,希尔排序可以用于大型数组,它对任意排列(不一定是随机的)的数组表现都很好。与归并、快速排序这些高效的算法相比,只要不是很大的 N(数组大小),它们可能只会比希尔排序快两倍(可能还不到),而且更复杂。总的来说,对于中等大小的数组,它的运行时间是可以接受的。代码量很小,且不需要使用额外的内存空间。

参考资源

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

0%