排序算法系列 05：希尔排序——给插入排序装个加速器
上一篇说了，插入排序在数据基本有序时非常快。那问题来了：如果数据很乱呢？
比如最小的数在数组最后面，插入排序得一步一步把它挪到最前面，中间所有元素都要移动一遍。太慢了。
希尔排序的想法很朴素：既然插入排序擅长处理基本有序的数据，那我先想办法让数据变得"大致有序"，再让插入排序收尾。
怎么让数据大致有序？答案是：先用大步长做分组插入排序，再逐步缩小步长。
核心思想
不一上来就相邻比较，而是先隔开一定间距分组，每组内部做插入排序。然后缩小间距，再排。最后间距缩到 1，就是普通插入排序——但这时候数据已经基本有序了。
举个直觉上的例子：一个很小的数在数组末尾，普通插入排序要挪 n 步才能到前面。但如果步长是 4，它一次就能跳 4 格，几步就到了大致正确的位置。
执行过程
用 [8, 5, 3, 1, 6, 9, 2, 7, 4] 跑一遍，数组长度 9。
第一趟，gap = 4：
按间隔 4 分组：
下标 0, 4, 8 → 元素 8, 6, 4
下标 1, 5 → 元素 5, 9
下标 2, 6 → 元素 3, 2
下标 3, 7 → 元素 1, 7
每组内部做插入排序，大元素和小元素之间的距离被快速拉近。
第二趟，gap = 2：
间距缩小，继续分组排序。数据更接近有序了。
第三趟，gap = 1：
就是普通插入排序。但因为前面两趟已经把数据调得差不多了，这一趟基本上只需要微调，跑得很快。
代码实现
function shellSort(arr) {
const result = [...arr];
let gap = Math.floor(result.length / 2);
while (gap > 0) {
for (let i = gap; i < result.length; i++) {
const current = result[i];
let j = i;
while (j >= gap && result[j - gap] > current) {
result[j] = result[j - gap];
j -= gap;
}
result[j] = current;
}
gap = Math.floor(gap / 2);
}
return result;
}
console.log(shellSort([8, 5, 3, 1, 6, 9, 2, 7, 4]));
// [1, 2, 3, 4, 5, 6, 7, 8, 9]
仔细看这段代码——它本质上就是插入排序，只不过把原来的 j - 1 换成了 j - gap。当 gap = 1 时，它和插入排序一模一样。
间隔序列怎么选？
上面用的是最简单的折半序列：n/2, n/4, n/8, ..., 1。
但这不是最优的。学术界研究了很多不同的间隔序列，比如 Knuth 序列（1, 4, 13, 40, 121, ...），不同序列会影响时间复杂度的上界。
对于入门来说，折半就够了。知道"间隔序列会影响性能"这个结论就行。
复杂度
| 情况 | 时间复杂度 |
|---|---|
| 最好 | 接近 O(n log n) |
| 平均 | 通常好于 O(n²)，取决于间隔序列 |
| 最坏 | 折半序列下可能 O(n²) |
空间复杂度 O(1)。
稳定性：不稳定。大步长交换可能让相等元素的相对顺序被打乱。
希尔排序的定位
说实话，在工程实践中，希尔排序用得不多。快速排序、归并排序在大多数场景下更优。
但希尔排序的价值在于这个思想：先粗调再细调。这种"先用大粒度处理，再逐步精细化"的策略在很多地方都能看到——比如图像处理的多分辨率金字塔、搜索引擎的分层索引。
另外它也是理解"为什么插入排序在基本有序时快"的最佳注脚——希尔排序就是在利用这个性质。
下一篇进入高级排序的领域：归并排序。从这里开始，时间复杂度会从 O(n²) 跳到 O(n log n)。
系列导航