希尔排序 Shell Sort
插入排序 · 用大间隔跳出 O(n²)
什么是希尔排序
希尔排序是插入排序的加速版。插入排序每次只和相邻元素比较，一个远在末尾的小元素要一格格挪很久。希尔的点子是：先用一个大的「间隔 gap」把数组分成若干组（每隔 gap 个取一个元素为一组），对每组各自做插入排序——这样元素能大步跨越、快速接近最终位置；然后缩小 gap 再来一轮，直到 gap=1 做最后一次普通插入。此时数组已「基本有序」，最后一趟极快。
它怎么做
外层 gap 逐轮减半（如 5 → 2 → 1），每个 gap 下对各分组做插入排序。点「下一步」看 [7, 6, 5, 10, 9, 8, 4, 3, 2, 1]：当前正在处理的那一组柱子高亮、其余淡出（dimmed）——你能清楚看到「隔着 gap 的元素凑成一组比较」，以及大间隔如何让逆序对被快速消除。
gap=5：步长减半，分 5 组
1function shellSort(a: number[]): number[] {
2 const n = a.length;
3 for (let gap = n >> 1; gap > 0; gap >>= 1) {
4 for (let start = 0; start < gap; start++) {
5 for (let i = start + gap; i < n; i += gap) {
6 const key = a[i];
7 let j = i;
8 while (j >= gap && a[j - gap] > key) {
9 a[j] = a[j - gap];
10 j -= gap;
11 }
12 a[j] = key;
13 }
14 }
15 }
16 return a;
17}
n10
gap5
group-
i0
key7
j0
a[j]7
shiftCount0
1 / 95
复杂度与适用
希尔排序不稳定、原地，时间复杂度取决于 gap 序列——本页用的减半序列约 O(n²) 最坏，而 Knuth、Sedgewick 等精心设计的序列可达 O(n^1.3) 上下。它是第一个突破「相邻交换类 O(n²)」的排序，证明了「先粗调、再细调」这一思路的威力；工程上偶尔用于中等规模、又想避免递归/额外内存的场景。
希尔 = 分组插入：gap>1 时各组内部就是普通插入排序；gap=1 那轮就是标准插入排序。
理解它的前提是先懂插入排序——希尔只是给插入排序加了「大间隔预处理」。
理解它的前提是先懂插入排序——希尔只是给插入排序加了「大间隔预处理」。
建议先看插入排序页，再回来体会希尔怎么用「间隔」给它提速；同一族的还有 二分插入排序（从比较次数下手优化）。