8. 希尔排序¶
8.1. 希尔排序¶
希尔排序得名于它的发明者 D.L. Shell，他在 1959 年首次发表了这种 算法。 它有时也被称为 递减增量排序 。 如果实现得当， 希尔排序 的性能会比插入排序或 选择排序这类 \(\theta(n^2)\) 排序好得多。 但它也比这些简单的 \(\theta(n^2)\) 排序稍微复杂一些。 与插入排序和选择排序不同，希尔排序背后没有现实生活中的直觉可以 启发——没有人会用希尔排序来整理自己的桥牌手牌或账单。 希尔排序的核心思想是利用插入排序的最好情况性能。 回忆一下，当线性表有序或近乎有序时，插入排序以线性时间运行。 所以希尔排序的策略是快速把线性表变得"大致有序"，从而让最后一次 插入排序完成任务。
希尔排序所做的和大多数优秀排序算法一样：把输入拆成若干部分，分别 排序，然后再合并起来。 但希尔排序的做法很特别，它把输入拆成一些常常并不连续的"虚拟" 子序列。 每个这样的子序列都用插入排序来排序。 然后选出另一组子序列进行排序，如此继续。
希尔排序在精心挑选的子序列上执行插入排序，先处理小的子序列，再 处理越来越大的子序列。 因此，在每一阶段，任何一次插入排序要么处理的是小线性表（因而很 快），要么处理的是近乎有序的线性表（因而同样很快）。
希尔排序把线性表拆成互不相交的子序列，子序列由一个"增量" \(I\) 定义。 给定子序列中的每条记录都相隔 \(I\) 个位置。 例如，如果增量为 4，那么子序列中每条记录都相隔 4 个位置。
希尔排序的一种可能实现是使用都是 2 的幂的增量。 我们先取小于 \(n\) 的最大 2 的幂作为 \(I\) 。 这会生成 \(I\) 个各含 2 条记录的子序列。 如果数组中有 16 条记录，下标从 0 到 15，那么最初会有 8 个各含 2 条 记录的子序列，子序列中的每条记录相隔 8 个位置。 第一个子序列是位置 0 和 8 上的记录。 第二个在位置 1 和 9，依此类推。
实际上，增量大小不必正好从 \(n/2\) 开始。 在下面的例子中，我们使用含 12 条记录的数组（因为 16 条记录会让 例子有点长）。 我们仍然从增量大小 8 开始。 当你点击浏览下面的幻灯片时，你会看到每个长度为 2 的子序列。 如果我们到达某一点，剩下的子序列只有一条记录（从记录 4 到 7 开头 的每个子序列都会如此），那么我们可以跳过对它们的处理。
希尔排序会用插入排序对这每一个长度为 2 的子序列进行排序。 当你点击浏览下一个幻灯片时，你会先看到当前子序列被高亮成黄色。 然后，待比较的一对记录会显示成蓝色。 如有必要就交换它们，使它们处于排序顺序。 （当然，由于这些最初的子序列长度都是 2，当比较这两个元素时，你 再也看不到任何黄色了！）
第一趟结束时，得到的数组"稍微更有序了一些"。
希尔排序的第二趟处理更少、更大的子序列。 在我们的例子中，第二趟的增量大小为 4，产生 \(n/4\) 个子序列。 由于例子中的数组有 \(n=12\) 条记录，所以我们有 4 个子序列，每个 含 \(12/4 = 3\) 条记录。 因此，第二趟的第一个子序列将是位置 0、4 和 8 上的 3 条记录。 第二个子序列将包含位置 1、5 和 9 上的记录，依此类推。
当你点击浏览幻灯片时，你会看到增量为 4 时的各个子序列。
每个含 3 条记录的子序列也会用插入排序来排序，如下所示。
处理完增量为 4 的子序列后，数组"更加有序了"。
第三趟将在增量为 2 的子序列上进行。 效果是我们处理 2 个线性表，一个由奇数位置组成，另一个由偶数位置 组成。 像往常一样，我们用插入排序对这些子序列排序。
此时，我们已经接近有序了。
希尔排序的最后一趟总是使用增量 1，也就是对所有记录进行一次"普通" 的插入排序。 但此时线性表比开始时接近有序得多，所以这最后一次插入排序调用比 在原始数组上运行插入排序快得多。
最后，数组就有序了。
下面是希尔排序的一种代码实现。
void shellsort(int[] A) {
for (int i=A.length/2; i>2; i/=2) { // For each increment
for (int j=0; j<i; j++) { // Sort each sublist
inssort2(A, j, i);
}
}
inssort2(A, 0, 1); // Could call regular inssort here
}
// Modified Insertion Sort for varying increments
void inssort2(int[] A, int start, int incr) {
for (int i=start+incr; i<A.length; i+=incr)
for (int j=i; (j>=incr) && (A[j] < A[j-incr]); j-=incr)
swap(A, j, j-incr);
}
void shellsort(T[] A) {
for (int i=A.length/2; i>2; i/=2) { // For each increment
for (int j=0; j<i; j++) { // Sort each sublist
inssort2(A, j, i);
}
}
inssort2(A, 0, 1); // Could call regular inssort here
}
/** Modified Insertion Sort for varying increments */
void inssort2(T[] A, int start, int incr) {
for (int i=start+incr; i<A.length; i+=incr)
for (int j=i; (j>=incr) && (A[j].compareTo(A[j-incr]) < 0); j-=incr)
swap(A, j, j-incr);
}
void shellsort(Comparable* A[], int n) {
for (int i = n/2; i > 2; i /= 2) //For each increment
for (int j = 0; j < i; j++) //Sort each sublist
inssort2(A, j, i, n);
inssort2(A, 0, 1, n);
}
// Modified Insertion Sort for varying increments
void inssort2(Comparable* A[], int start, int incr, int n) {
for (int i = start+incr; i < n; i += incr)
for (int j = i; ((j >= incr) && (*A[j] < *A[j-incr])); j -= incr)
swap(A, j, j-incr);
}
现在，测试一下你对子序列概念的理解。
8.2. 融会贯通¶
增量序列的选取有很大的灵活性。 它不必从小于 \(n\) 的最大 2 的幂开始，每次再减半。 事实上，那甚至不是一个好的增量序列选择。 我们稍后会回到这一点。 现在，你只需明白：只要每个增量都比前一个小，并且最后一个增量是 1， 希尔排序就能正常工作。
现在，试着在你选定大小的数组上运行希尔排序，值可以是随机的，也 可以是你自己选择的。 你还可以设置增量序列。 用这个可视化来确保你理解希尔排序的工作原理。
接下来，我们来复习什么样的增量序列是合法的。
8.3. 希尔排序练习¶
现在测试一下自己，看看你对希尔排序的理解程度。 你能重现它的行为吗？
8.4. 优化希尔排序¶
增量序列的某些选择会让希尔排序比其它选择更高效。 特别地，上面描述的增量选择 \((2^k, 2^{k-1}, \ldots, 4, 2, 1)\) 结果相对低效。 例如，你应当注意到，给定 8 增量子序列中的所有记录也都属于某个 4 增量子序列，而这些记录又都依次属于同一个 2 增量子序列。 所以随着增量减小，子序列之间没有"交叉"。 一个更好的选择是基于 "\(3n+1\)" 的如下序列： (..., 121, 40, 13, 4, 1)。 另一种做法是确保各个增量两两互素。 序列 (..., 11, 7, 3, 1) 就是一个例子。 在这种情况下，不同增量大小下的线性表之间有大量"交叉"。
现在你可以尝试不同的增量序列，看看它们如何影响希尔排序的代价。
对希尔排序做理论分析很困难，所以我们不得不不加证明地接受：对于 合理的增量序列，希尔排序的平均情况性能是 \(\Theta(n\sqrt{n}) = \Theta(n^{1.5})\) 。 因此，希尔排序比插入排序或前面介绍的任何其它 \(\theta(n^2)\) 排序都要好得多。 事实上，当 \(n\) 为中等规模时，希尔排序比后面将要介绍的渐近 更优的排序算法也差不了太多（不过如果这些算法实现得好，它往往还是 略慢一些）。 希尔排序展示了我们有时如何利用某个算法（这里是插入排序）的特殊 性质，即使这个算法在一般情况下慢得不可接受。
8.5. 希尔排序小结问题¶
下面是一些复习题，用来检查你对希尔排序的理解。
