希尔排序详解：从增量序列到工程实践与性能对比

这个系列写到第44篇，终于轮到希尔排序了。如果你已经能闭着眼写出插入排序，却发现它在乱序大数组上慢得让人着急，那希尔排序就是你应该掌握的下一课。它不依赖递归，没有额外内存开销，代码量只比插入排序多一层循环，却能把随机数据的排序效率提升一个量级。与快排、归并这类“分而治之”的思路完全不同，希尔排序走的是一条很朴素的路线：先让整个数组在大范围内接近有序，再逐步缩小粒度，最后一轮用插入排序收尾。

这篇博文不打算只贴一段代码就完事。我尽量把“为什么要用增量”“增量到底怎么选”“代码怎么写才不容易错”以及“我在实际调试中踩过的坑”一次性讲清楚。适合的读者大概是三类：刚把插入排序吃透的初学者；准备算法面试、想把排序专题串成一棵树的开发者；以及在做嵌入式或写脚本工具时，想找一个“无递归、原地、代码极简”排序方案的人。

1. 为什么必须先吃透插入排序，才能搞懂希尔排序

1.1 插入排序的真正瓶颈：不是比较次数，而是移动次数

插入排序的思路很简单：从左往右处理每个元素，把它插入到左侧已经有序的序列中。很多人以为它的开销主要来自比较，但在实际运行中，真正拖垮性能的是元素的搬移。每插入一个新元素，往往要把前面一大段比它大的元素统统往后挪一格，这个挪动次数用掉的时间比比较多得多。

举个极端例子，对一个完全逆序的长度为 n 的数组做插入排序，比较次数和移动次数都在 n²/2 这个量级。当 n 到十万级别时，总操作次数高达数十亿次，哪怕用编译型语言跑，也要等上好几秒甚至十几秒。但如果数组已经接近有序，插入排序的移动量会骤降到接近 n，速度快得惊人。

这个反差给了我们一个重要提示：插入排序是一个“吃软不吃硬”的算法，它在基本有序的数据上非常高效。希尔排序的所有设计，都是围绕这一点展开的。

1.2 希尔排序的切入点：用“分组 + 间隔”降低整体移动量

希尔排序的核心思想是：与其一上来就做严格的全局插入排序，不如先在宏观尺度上做几轮“粗糙的排序”，让数据呈现出整体上的有序趋势，再交给插入排序进行最后一轮精细加工。

具体做法是设置一个间隔 gap。在每一轮中，把所有相距 gap 的元素看作一组，分别对每一组做插入排序。比如 gap = 4 时，索引 0、4、8 是一组，索引 1、5 是一组，索引 2、6 是一组，索引 3、7 是一组。每一组内部排好序以后，整个数组虽然还没有完全有序，但每个元素已经大概率离它该待的位置不远了。然后再把 gap 缩小，比如从 4 变成 2，重新分组排序。最后 gap = 1，这时候数组已经基本有序，插入排序只需要做很少的移动就能完成最终收尾。

希尔排序最鸡贼的地方就在这里：大间隔阶段付出的移动代价，换来了全局的大幅有序；而最后的小间隔阶段，又享受了插入排序“在近有序数据上接近线性”的红利。全程没有引入新的数据结构，只用了一个整数变量来记录间隔。

1.3 “局部有序”是希尔排序的灵魂

很多人初次看希尔排序的代码会困惑：每一轮排完以后，数组看起来还是乱糟糟的，到底排了个什么？

这里要理解一个概念：gap 有序。当一轮结束之后，数组满足这样一个性质：对于任意位置 i，都有 arr[i] <= arr[i + gap]。也就是说，每个元素与它前面间隔 gap 的那个元素是有序的。这个性质不像全局有序那么严格，但它意味着元素不会出现“横跨很远还大小颠倒”的情况。

正是这些逐步收紧的 gap 有序状态，让最后 gap = 1 的那一轮插入排序变得特别轻松。我不止一次在调试时把每一轮中间结果打印出来看，你会发现一个很有意思的现象：数组在 gap 很大的时候，元素一下就从一头蹦到了很靠前的位置；随着 gap 缩小，每个元素只是在小范围内微调。这种“大跨度纠正、小范围微调”的组合，才是希尔排序真正的灵魂。

2. 核心实操：增量序列选型与实现细节

2.1 增量序列有哪些，差别在哪

gap 的取法直接决定了希尔排序的性能，这也是它最值得展开聊的地方。我见过太多人直接用 gap = n/2，然后每次除以 2，稀里糊涂写完就以为万事大吉。实际上，增量序列的选择对复杂度的形响，比很多人想象的大得多。

为什么增量序列会影响性能？关键在“分组之间”的交互频率。希尔增量让每轮的分组相对固定，某些排列下会出现元素只在同一组内循环，迟迟无法与其它组的元素交换的情况，导致大量无效比较。而 Knuth、Hibbard 这些序列让不同轮次的分组差异足够大，元素有机会在更广的范围内交换位置，排序效率明显提升。

我的建议是：如果你不想研究一堆数学序列，直接用 Knuth 增量。它代码量增加不到几行，平均性能却明显优于经典的折半希尔增量。如果你追求的是“几乎最优”的工程表现，Sedgewick 增量是更好的选择。

2.2 为什么说“插入排序 + 大间隔”减少了移动次数

这里我用一个粗糙的估算来说明问题。假设数组长度 n = 10 万，初始完全逆序。用普通插入排序，插入第 i 个元素平均要移动约 i/2 个位置，总移动次数大概是 n²/4，数量级在 25 亿左右。

再用一个简单的希尔增量走一遍。第一轮 gap = 5 万，每组只有一两个元素，几乎不花代价；第二轮 gap = 2.5 万，同样很轻；到 gap 几千的时候，组数变多，每组元素数也在变多，但每个元素移动的跨度已经大幅缩短。因为前几轮大间隔已经把每个元素推进到了距离最终位置不远的地方，后面小间隔阶段每轮移动的总距离，加起来远小于初始逆序状态下的 n²/4。

这里有个更直观的理解方式：大间隔阶段，一次交换可以直接跨越整个数组的很大一段距离，相当于先用“大步”把所有元素带到大致应该待的区域；小间隔阶段再用“小碎步”精调。这比插入排序从头到尾都只用“一格一格挪”少走太多冤枉路。

有人可能会问：多轮插入排序加起来，难道不会抵消掉好处吗？实际不会。只要增量序列设计合理，每轮操作的复杂度大致按 n 乘以一个递减的系数来增长，而最终总工作量远低于单轮乱序插入排序，这也是希尔排序为什么能在中等规模数据上长期保持竞争力的根本原因。

2.3 三层循环怎么写不出错

希尔排序的经典实现是一个三层嵌套循环，这也是第一次写它的人最容易绕晕的地方。我先给一个最标准的模板，再拆开讲每一步为什么这么写。

void shell_sort(int arr[], int len) { for (int gap = len / 2; gap > 0; gap /= 2) { for (int i = gap; i < len; i++) { int temp = arr[i]; int j = i; while (j - gap >= 0 && arr[j - gap] > temp) { arr[j] = arr[j - gap]; j -= gap; } arr[j] = temp; } } }

很多人写的时候容易走两个极端：要么把中层循环写成“按组别来”，先遍历所有组，再遍历组内元素；要么觉得内层 while 只有“从后往前找”一个方向，结果把边界条件写错。

关键在于第二层循环为什么从 gap 开始，而不是 0。因为插入排序的处理逻辑是对“每个新元素”做插入：索引 i 之前的同组元素已经有序，我们把 arr[i] 提取出来，向前隔 gap 找位置。当 i 从 gap 遍历到 n-1 时，每一组在“每一轮 i 递增”的过程中都被自然地处理了，不需要单独维护组的索引。这比“显式按组循环”写法更紧凑，也不容易漏组。

内层 while 的边界条件 j - gap >= 0 是重中之重。它保证我们在查找过程中不会越过数组边界。很多人调参时把这里的 arr[j - gap] > temp 写成 >=，虽然代码也能跑，但会把排序性质变为不稳定，而且还多做了无谓的相等交换。

3. 从零实现一次完整的希尔排序过程

3.1 手工推演一轮：看看动态过程

光讲理论不够，我带你看一组实际推演。假设数组为：

原始：[9, 1, 5, 8, 3, 7, 4, 6, 2]。n = 9，按折半增量：

第一轮 gap = 4，分为四组：

• 索引 0、4、8：元素 9、3、2，组内插入排序后变为 2、3、9
• 索引 1、5：元素 1、7，不变
• 索引 2、6：元素 5、4，排序后变为 4、5
• 索引 3、7：元素 8、6，排序后变为 6、8

这一轮结束后数组变成：[2, 1, 4, 6, 3, 7, 5, 8, 9]。你可以看到 9 被直接推到了最后，2 从开头冲到了最前面，这就是大步长交换的威力。

第二轮 gap = 2，分为两组：

• 索引 0、2、4、6、8：元素 2、4、3、5、9，排序后变为 2、3、4、5、9
• 索引 1、3、5、7：元素 1、6、7、8，保持不变

这一轮结束后数组变成：[2, 1, 3, 6, 4, 7, 5, 8, 9]。

第三轮 gap = 1，就是标准的插入排序。由于前两轮已经让数组非常接近有序，这一轮只需要轻微移动，最终得到：

[1, 2, 3, 4, 5, 6, 7, 8, 9]

手工推演一遍以后，你大概能直观体会到希尔排序“先粗排后精排”的过程。我把这个推演过程打出来贴在自己的笔记里，每次看都觉得很能说明问题：它不像快排那样一次划分就要确定一个元素的最终位置，而是让所有元素在好几轮里共同逼近最终位置。

3.2 两种实现方式：交换法与移动法

希尔排序有两种常见写法，一种是组内用“相邻交换”的方式推进，一种是沿用插入排序里“暂存 + 后移”的方式。两者结果一样，但性能差距不小。

交换法的思路是，在组内做类似冒泡的连续交换，写起来很直观，但每次交换都涉及三次赋值，而且相邻比较、相邻交换的模式虽然逻辑正确，却牺牲了插入排序“一次后移多位、最后只写一次”的优势。

移动法就是我们第一节代码里的写法：先把当前元素暂存到 temp，然后把组内前面比它大的元素依次向后覆盖，最后把 temp 写进空出来的位置。这样每个元素在每轮排序中最多被复制一次，整体赋值次数比交换法少一个量级。

我用同样的随机数据集对比过这两种写法，差距很明显。在十万级数据上，交换法比移动法慢大约 30% 到 50%。对于现代 CPU 来说，赋值操作的 cache 压力和指令数都会被放大，所以这个优化不是“微优化”，而是值得养成习惯的实现方式。

另外补充一个稍微进阶的思路：如果数据量不大，可以用带哨兵的数组下标处理来减少边界判断。但因为希尔排序下标是跳跃的，哨兵位置不好放，工程中一般不这么干，我也不会在普通任务里强行套用。

3.3 复杂度与稳定性：一个表讲清楚

很多人面试时被问希尔排序的复杂度，容易含糊其辞。我直接整理成一张表，方便你记忆：

稳定性这块很多人会想当然地认为：既然最后一轮是插入排序，而插入排序是稳定的，那希尔排序也应该稳定。这是个很常见的误区。因为在 gap 大于 1 的阶段，相等的元素可能被分到不同的组，也可能因为一次跨 gap 的移动直接越过另一个相等元素，相对次序已经变了；最后一轮的插入排序只保证不主动破坏现有的相等元素顺序，却无法逆转前面轮次里已经发生的交错。

举个最简单的直观理解方式：插入排序稳定，是因为它每次只移动一步，比较相邻元素；而希尔排序一次跳跃多个位置，跳跃过程中跳过了谁，相对顺序就已经被改写了。所以任何需要保持原始相等元素顺序的业务场景，都不要选希尔排序，直接考虑归并排序更稳妥。

4. 常见问题与调优实战

4.1 新手最容易掉的三个坑

第一个坑是外层循环的 gap 更新放错位置。比如有人在 gap /= 2 之后才进入内层循环，导致 gap 一直在变，内层循环逻辑混乱。标准写法应该严格按照“确定本轮 gap -> 执行该轮所有插入排序 -> 缩小 gap”的顺序。

第二个坑是 while 循环里忘记判断下界。如果写成 while (arr[j - gap] > temp) 而 j 已经小于 gap，数组就越界访问了，结果不确定，可能崩溃也可能产生脏数据。这个错误在调试时很隐蔽，因为越界不一定立刻报错，而是污染了相邻内存区域。

第三个坑是把比较条件 arr[j - gap] > temp 误写成 >=。从功能上说排序结果依然正确，但稳定性更差，而且增加了无意义的相等元素交换，会在有大量重复元素的数组上产生额外的性能开销。还有人在内层循环结束后忘了把 temp 写回 arr[j]，导致原数组对应位置丢失数据。

我的经验是，初学阶段最好在每一轮 gap 结束时打印一次数组状态，与手工推演结果对照，能很快定位是哪一层循环出了问题。写完以后再用全零、全一等边界数组测一遍，能过滤掉很大一部分越界和逻辑漏洞。

4.2 性能实测与数据

我习惯用一个固定数据集来给排序算法做基准，这样对比才有说服力。下面是我本地用 C 语言在 10 万元素随机数组上测过的一组量级数据，仅供参考，因为不同机器差异很大：

这组对比能说明几个问题。第一，希尔排序在随机数据上完全碾压插入排序，而且在十万级规模下依然保持可接受的速度，这是它最大的价值区间。第二，快速排序仍然更快，尤其在大数据集上优势明显。第三，在近乎有序的数据上，插入排序的表现极其强悍，甚至不输希尔排序，这说明希尔排序并不是一个“所有场景都更优”的算法。

如果数据规模到了百万级，我会果断选快排或者归并；但如果是几十万以内、内存紧张、或者需要一个无递归实现，希尔排序往往是最省心的选择。

4.3 工程选型：什么时候用希尔排序

根据我的实际经验，可以给出这样的选型建议：

希尔排序还有一个很少被提到的优势：它对缓存相对友好。因为它始终在一个数组内通过下标跳跃访问，没有额外分配大块内存，所以在内存带宽受限的场景下，它的表现往往比理论复杂度更让人满意。

我在写某个轻量级工具时，处理的数据量大约三四十万条，要求不引入第三方库，也不想递归引发栈问题，当时直接用了 Knuth 增量的希尔排序，实测结果完全够用，代码只有十几行，后面维护的人一眼就能看懂。这种“不追求极限速度，但要极简可控”的场景，就是希尔排序的舒适区。

4.4 一条经常被忽略的经验

最后分享一个从实践中得来、但常被教程忽略的细节：增量序列和数据的组织方式要匹配。

如果你排序的是“几乎有序且长度很大”的数组，用折半增量其实效果不差，因为第一轮大间隔就能把大多数元素送到正确位置附近。但如果数据是“逆序程度很高的随机排列”，折半增量会导致过早进入小间隔阶段，让大量元素在小范围内反复移动，这时候用 Knuth 增量效果更好，因为它从更大间隔起步，宏观纠正能力更强。

另外，在数组长度小于某个阈值时，希尔排序的额外循环开销反而会拖累性能。我通常会在排序函数开头加一个判断，当长度小于 16 或 20 时直接走插入排序。这种“阈值切换”的思路在工程里很常见，虽然只涉及几行代码，但能让整体表现更平滑。

还有一点是关于增量序列的生成。如果你使用 Knuth 增量，生成序列时常用的代码是：

gap = 1 while gap < n // 3: gap = gap * 3 + 1

然后每轮循环结束再反过来 gap = (gap - 1) // 3。这样能保证最后一步一定是 gap = 1，不会把数组排成一个“不完全有序”的状态。这个收尾步骤是必须的，否则前面对数组做的所有“半有序”工作都会浪费，算法就不是一个完整的排序算法。

如果只是写一次性的脚本，佛系一点用 gap = len(arr) // 2 也无所谓；但如果这个排序会成为工具链的一部分，我建议老老实实把 Knuth 增量实现出来，代码多不了几行，性能却更可靠。排序这种基础操作，稳定性和可预期性比那一点点代码复杂度重要得多。

在我实际使用中，最舒服的方式是把排序函数封装成“内部带阈值切换 + Knuth 增量”的版本，所有逻辑控制在一个文件里，注释写清楚，后续接手的人不用猜增量为什么这么取。毕竟算法题里背代码只是第一步，能解释清楚每一步在干什么，才有资格说真正掌握了它。