间隔序列：决定性能的关键
基于通用算法套路 · 核于 2026-07
速查
- gap 序列决定复杂度：希尔排序的时间复杂度完全取决于 gap 序列的选择——同一个「分组插入」框架，换一套 gap 序列，最坏复杂度可能从 O(n²) 降到 O(n^1.3)。这是希尔排序最核心、也最独特的特性。
- Shell 原版序列：
n/2, n/2/2, …, 1（即gap = gap >> 1，每次减半）。最简单直观，但最坏仍 O(n²)——存在精心构造的输入让它在某些 gap 上的子序列恰好全逆序。 - Knuth 序列：
1, 4, 13, 40, 121, …（递推h = 3h + 1，从 1 倒推到不超过 n）。最坏 O(n^1.5)，且工程实现简洁，是教科书和库实现的常用选择。 - Sedgewick 序列：
1, 5, 19, 41, 109, …（由9×4^k − 9×2^k + 1与4^k − 3×2^k + 1交错合并）。平均约 O(n^(4/3))，是目前实际表现最好的序列之一。 - 为何 gap 必须互质/有特定结构：若 gap 序列之间有公因子（如都是偶数），元素会反复在固定的少数几个位置间移动，无法充分「打散」；好的序列让各轮的分组互相错开，覆盖所有位置。
- gap 必须缩到 1：gap=1 是正确性的兜底（普通插入排序消除所有相邻逆序）；任何 gap 序列的最后一项都必须是 1。
- 统一代码框架：外层遍历 gap 序列，内层是「把 gap 当步长的插入排序」——换序列只改外层 gap 的取值，内层逻辑完全不变。
- 无「最优」序列：希尔排序 gap 序列的最坏复杂度至今是数学上的开放问题，没有严格证明的下界；O(n^1.3) 等多为经验值。
- 进阶顺序：性能分析 → 参考。
一、为何 gap 序列决定复杂度
希尔排序的框架是固定的：多轮插入排序，gap 从大到小。但「取哪些 gap 值」直接影响每一轮的工作量和总效果。考虑两个极端：
- 差的序列（如 gap 之间有公因子）：各轮分组高度重叠，元素在固定位置间反复横跳，总比较次数退化到 O(n²)。
- 好的序列（如互质或有精巧递推）：各轮分组互相错开，每轮都在前一轮基础上有效推进，总比较次数降到 O(n^1.3) 左右。
这正是 Shell 原版（n/2 减半）最坏仍是 O(n²)、而 Sedgewick 序列能到 O(n^1.3) 的原因——算法骨架相同，性能差异完全来自 gap 取值。这是希尔排序区别于其他排序（如快排的复杂度由 pivot 决定）的独特之处：它的「调参」就是选 gap 序列。
二、Shell 原版序列：最简单的 O(n²)
Donald Shell 最初提出的序列就是每次减半：
gap = n/2, n/4, n/8, …, 1 （gap = gap >> 1，直到 gap = 0）for (let gap = n >> 1; gap >= 1; gap >>= 1) {
for (let i = gap; i < n; i++) {
const tmp = a[i];
let j = i;
while (j >= gap && a[j - gap] > tmp) { a[j] = a[j - gap]; j -= gap; }
a[j] = tmp;
}
}- 优点：实现极简（一行
gap >>= 1），易记易写。 - 缺点：最坏 O(n²)。原因是 gap 取值都是 2 的幂，它们之间有公因子 2——存在精心构造的输入（让某些子序列在多个 gap 下都全逆序），导致总比较次数退化。
- 实际表现：对随机数据仍比插入排序快得多（接近 O(n^1.3) 的实际体验），但最坏情况不保证。
三、Knuth 序列：最坏 O(n^1.5) 的工程选择
Knuth 提出用 h = 3h + 1 递推生成序列，让相邻 gap 互质（3 倍关系），避免公因子问题：
序列：1, 4, 13, 40, 121, 364, … （h_{k+1} = 3·h_k + 1）
取法：从最大的「不超过 n/3」的 h 开始，逐步除以 3（向下取整）缩到 1// 先生成不超过 n 的最大 h
let h = 1;
while (h < n / 3) h = 3 * h + 1; // 1, 4, 13, 40, … 取最大的 < n/3
for (; h >= 1; h = Math.floor(h / 3)) {
for (let i = h; i < n; i++) {
const tmp = a[i];
let j = i;
while (j >= h && a[j - h] > tmp) { a[j] = a[j - h]; j -= h; }
a[j] = tmp;
}
}- 最坏复杂度 O(n^1.5)：Knuth 证明了用这个序列，最坏情况是 O(n^1.5)——比 Shell 原版的 O(n²) 严格更优。
- 工程友好：递推简单（
3h+1），只需一个 while 预算最大 h，内层与 Shell 原版完全一致。是许多教科书和库的默认选择。 - 平均约 O(n^1.25)：经验上对随机数据表现良好。
四、Sedgewick 序列：实际最快的 O(n^1.3)
Sedgewick 通过大量实验和数论分析，提出一个由两个公式交错合并的序列，是目前实际表现最好的之一：
序列：1, 5, 19, 41, 109, 209, 505, 929, …
生成：偶数项 9×4^k − 9×2^k + 1（k=0,1,2,…）= 1, 19, 109, 505, …
奇数项 4^(k+2) − 3×2^(k+2) + 1（k=0,1,2,…）= 5, 41, 209, 929, …
交错合并并去重排序// 预先生成不超过 n 的 Sedgewick 序列（降序使用）
const gaps = [];
let k = 0;
while (true) {
const a = 9 * (1 << (2 * k)) - 9 * (1 << k) + 1; // 9·4^k − 9·2^k + 1
const b = (1 << (2 * k + 4)) - 3 * (1 << (k + 2)) + 1; // 4^(k+2) − 3·2^(k+2) + 1
if (a <= n) gaps.push(a);
if (b <= n) gaps.push(b);
if (a > n && b > n) break;
k++;
}
gaps.sort((x, y) => y - x); // 降序，从大到小用
for (const gap of gaps) {
for (let i = gap; i < n; i++) {
const tmp = a[i];
let j = i;
while (j >= gap && a[j - gap] > tmp) { a[j] = a[j - gap]; j -= gap; }
a[j] = tmp;
}
}- 平均约 O(n^(4/3)) ≈ O(n^1.33)：实验和部分理论分析显示，这是目前序列中平均表现最好的之一。
- 最坏 O(n^(4/3))：已证明的最坏上界也优于 Knuth 的 O(n^1.5)。
- 代价：序列生成稍复杂（两个公式交错），但性能收益明显，适合对速度有要求的场景。
五、各 gap 序列性能对比
| gap 序列 | 典型取值 | 最坏复杂度 | 平均（经验） | 特点 |
|---|---|---|---|---|
| Shell 原版 | n/2, n/4, …, 1 | O(n²) | ~O(n^1.3) | 最简单，最坏会退化 |
| Hibbard | 2^k − 1 | O(n^1.5) | ~O(n^1.25) | 相邻互质 |
| Knuth | 3h+1（1,4,13,40,…） | O(n^1.5) | ~O(n^1.25) | 教科书常用，工程友好 |
| Sedgewick | 9·4^k−9·2^k+1 等 | O(n^(4/3)) | ~O(n^(4/3)) | 实际最快之一 |
| Pratt | 2^p·3^q | O(nlog²n) | O(nlog²n) | 理论好但项数多、常数大 |
选型建议：教学/快速实现用 Shell 原版（够直观）；工程默认用 Knuth 序列（平衡）；追求极致性能用 Sedgewick 序列。
六、为何 gap 之间需要「互质」
如果 gap 序列的所有值都有公因子（比如 Shell 原版全是 2 的幂），那么各轮的分组在数学上是高度相关的——某些下标组合永远不会被同一轮处理，导致这些位置的逆序对要等到 gap=1 才能消除，退化成插入排序的 O(n²)。
好的 gap 序列让相邻两个 gap 互质（如 Knuth 的 3 倍关系、Hibbard 的 2^k−1），这样每一轮的分组都和前一轮错开，能持续处理新的逆序对，避免「原地踏步」。这是 Knuth/Sedgewick 序列优于 Shell 原版的本质原因——不是 gap 的数值大小，而是它们之间的数论关系决定性能。
交互演示
- 希尔排序可视化演示 —— 不同 gap 序列下分组插入的对比
下一步
理解了 gap 序列如何决定复杂度后，下一步是深入性能分析——为何跨距离交换能突破 O(n²)、平均 O(n^1.3) 从何而来、以及与各排序的横向对比，见性能分析。