入门：分组插入、缩小增量与突破 O(n²)
基于通用算法概念 · 核于 2026-07
速查
- 定义：希尔排序是插入排序的推广——把数组按一个间隔（gap）分成 gap 个交错子序列，每个子序列各自做插入排序；然后让 gap 逐步缩小（n/2 → n/4 → … → 1），gap=1 时退化为一次普通插入排序，此时数组已近乎有序，一遍扫完。
- 核心动机：插入排序对「近乎有序」的数组是 O(n)，但对「相距终位很远」的元素只能相邻交换（一步挪一格），效率被拖垮成 O(n²)。希尔排序让相距 gap 的元素能跨距离交换（一次跨越多步），快速接近终位。
- 分组方式：gap=g 时，下标
i与i+g、i+2g、… 属于同一子序列。共 g 个子序列（起点分别为0, 1, …, g-1），每个子序列内部独立做插入排序。 - 为何能突破 O(n²)：大 gap 阶段让远距离元素「大跨步」就位（一次交换顶插入排序的多次相邻挪动），小 gap 阶段做微调；等到 gap=1 时数组已基本有序，插入排序近乎 O(n)。整体平均约 O(n^1.3)（依赖 gap 序列）。
- gap=1 即插入排序：当 gap 缩到 1，希尔排序就是标准的插入排序——所以「希尔是插入的推广，插入是希尔的特例（只有 gap=1 一轮）」。
- 复杂度依赖 gap 序列：Shell 原版（n/2, n/4, …, 1）最坏 O(n²)；Knuth 序列（1, 4, 13, 40, …，
h = 3h+1）最坏 O(n^1.5)；Sedgewick 序列平均约 O(n^(4/3))。没有数学证明上的「最优序列」，至今是开放问题。 - 原地、不稳定：只需 O(1) 额外空间；但分组后相等元素可能跨子序列交换，相对次序被打乱，不稳定。
- 最好情况：输入已有序时，每一轮插入排序都触发「立即 break」（当前元素 ≥ 前驱），总比较约 O(nlogn)（log n 轮各 n 次），即 最好 O(nlog²n) ~ O(nlogn)。
- 何时实用：n 为几百到几千的中等规模数据、嵌入式/资源受限环境、库排序对小数组的兜底——常数小、无递归、原地，实测常常快于堆排。
- 与插入排序关系：希尔 = 多轮（gap 从大到小）插入排序；插入 = gap 序列只有 {1} 的希尔。记住「gap 大步粗调，gap=1 微调收尾」。
- 进阶顺序：间隔序列 → 性能分析 → 参考。
一、从插入排序的痛点说起
插入排序的核心操作是：把当前元素 a[i] 与它左边的已排序段从右向左比较，遇到比自己大的就右移一格，直到找到合适位置插入。它对近乎有序的数组极快（每个元素只需比较一两次就 break，接近 O(n)），但有一个致命弱点——只能相邻交换：
极端例子：最小元素在数组末尾
[5, 4, 3, 2, 1] ← 逆序，1 在最后
处理 1 时：1 要依次和 2、3、4、5 比较并左移 4 次（一步一格）
n 个元素全逆序 → 总移动 1+2+…+(n-1) = O(n²)问题在于：元素 1 明明离终位（下标 0）很远，却只能一步挪一格，要挪 n-1 次。如果能让它一次跨越多步直接接近终位，就能大幅减少移动次数——这正是希尔排序的出发点。
二、分组插入：让元素跨距离交换
希尔排序引入一个间隔 gap：不再比较相邻元素（gap=1），而是比较相距 gap 的元素。具体做法是按下标对 gap 取模分组——下标 i 与 i+g、i+2g、… 属于同一组，共 gap 组，每组内部独立做插入排序（比较的是相距 gap 的元素，而非相邻元素）。
原数组：[8, 1, 5, 7, 4, 3, 6, 2]，n=8
gap=4 分组（共 4 组，相距 4 的元素为一组）：
组 0（下标 0,4）： [8, 4] → 排序 → [4, 8]
组 1（下标 1,5）： [1, 3] → 排序 → [1, 3]
组 2（下标 2,6）： [5, 6] → 排序 → [5, 6]
组 3（下标 3,7）： [7, 2] → 排序 → [2, 7]
一轮后：[4, 1, 5, 2, 8, 3, 6, 7]
（元素 8、7 都大跨步向右移，2、4 快速接近终位）
gap=2 分组（共 2 组）：
组 0（下标 0,2,4,6）：[4, 5, 8, 6] → [4, 5, 6, 8]
组 1（下标 1,3,5,7）：[1, 2, 3, 7] → [1, 2, 3, 7]
一轮后：[4, 1, 5, 2, 6, 3, 8, 7]
gap=1：普通插入排序，数组已基本有序，一遍扫完
最终：[1, 2, 3, 4, 5, 6, 7, 8]关键观察：gap=4 那一轮，元素 8 从下标 0 直接跳到下标 4（跨了 4 步），元素 2 从下标 7 跳到下标 3（跨了 4 步）。如果用插入排序，它们要一格一格挪，各挪 4 次。希尔排序用一次「跨距离交换」完成了同样的事。
三、gap 从大到小：先粗调后微调
希尔排序的精髓是多轮插入排序，gap 从大到小：
- 大 gap（粗调）：让相距很远的元素快速接近各自的终位区域。这一步移动次数少（每组元素少），但每次交换跨度大，迅速消除「远距离逆序」。
- 中 gap（逐步收紧）：在前一步的基础上继续细化，让元素在更小范围内就位。
- gap=1（微调收尾）：普通插入排序。但此时数组已经近乎有序（前面几轮已经把元素大致摆好），插入排序在近乎有序数组上是接近 O(n) 的——这正是希尔排序「最后一轮很便宜」的原因。
为何 gap 必须缩小到 1？ 只有 gap=1 的普通插入排序能保证任意相邻逆序对都被消除，从而得到完全有序的数组。gap>1 时各子序列独立，无法消除「跨组」的相邻逆序。所以 gap=1 是正确性的兜底，不可省略。
四、gap=1 即插入排序：希尔的特例关系
把希尔排序的 gap 序列设成只有 {1}（即只跑一轮 gap=1），它就完全等价于插入排序。这给出了两者的关系：
- 插入排序 = 希尔排序 gap 序列为
{1}的特例。 - 希尔排序 = 多轮插入排序（gap 从大到小，最后一轮必为 1）的推广。
插入排序（gap=1 的内层）：
for (let i = 1; i < n; i++) {
const tmp = a[i];
let j = i;
while (j > 0 && a[j-1] > tmp) { a[j] = a[j-1]; j--; } // 相邻比较
a[j] = tmp;
}
希尔排序（套一层 gap 循环，内层把 1 换成 gap）：
for (let gap = n >> 1; gap >= 1; gap >>= 1) { // gap 从 n/2 缩到 1
for (let i = gap; i < n; i++) { // 注意从 gap 开始
const tmp = a[i];
let j = i;
while (j >= gap && a[j-gap] > tmp) { a[j] = a[j-gap]; j -= gap; } // 跨 gap 比较
a[j] = tmp;
}
}内层 while 把插入排序的 a[j-1] 换成 a[j-gap]、j-- 换成 j -= gap——就这么一处改动，外面包一层 gap 循环，就是希尔排序。
五、为何比插入排序快：跨距离交换快速就位
回到最初的问题——插入排序对逆序数组是 O(n²)，因为它只能相邻挪动。希尔排序通过跨距离交换解决了这个痛点：
- 插入排序：元素每次只能挪动 1 步，把末尾的最小元素挪到首位要 n-1 次比较移动。
- 希尔排序：大 gap 阶段元素每次能挪动 gap 步，n/2 个元素各挪 n/2 步就能大致就位——总移动次数从 O(n²) 降到约 O(n^1.3)。
直观理解：希尔排序先花少量大跨步把元素搬到正确的「大区域」，再逐步缩小步长做精细调整。每一轮都在前一轮「已经较好」的基础上工作，而不是像插入排序那样从零开始一格一格挪。这种「先粗后细」的分层策略，是它能突破 O(n²) 的本质原因。
注意：希尔排序没有严格的数学证明给出某个 gap 序列的最坏复杂度——O(n^1.3) 等数字多为经验值和特定序列的已证上界。这是它「理论上不那么干净」但「工程上很实用」的原因。
下一步
理解了希尔排序的分组插入思想与缩小增量后，下一步是看决定性能的 gap 序列——Shell 原版、Knuth、Sedgewick 等不同序列的差异与选择，见间隔序列。