1. 从插入排序的死角说起希尔排序到底在优化什么1.1 一个被低估的事实插入排序在近乎有序的数据上快得离谱写 C/C 的人手头多少都攒着几个排序函数冒泡、选择、插入这三样通常是最早写的。但真到看代码量的时候多数人会得出同一个结论插入排序是这三个里面唯一还能在生产代码里露面的。原因不复杂——它的时间复杂度虽然写着 O(n²)但那个 n² 只在最坏情况下才成立。如果数组本来就接近有序插入排序的实际循环次数会退化到接近 n 的量级跑起来比很多花里胡哨的算法还快。我用一个具体数字说明这件事。假设一个长度一万的数组每个元素距离它最终位置平均只差 5 个位置那么插入排序总共要做的元素搬移次数大约就是 5 万次而不是 1 亿次。这种局部有序的输入在实际工程里非常常见日志按时间戳追加、增量更新的配置表、从有序文件里合并来的数据都长这个样子。问题也恰恰在这里。插入排序的机制是拿一个元素往前逐个比对、逐个后移它每次只能跨越一个位置。一个原本在数组末尾、却应该排到最前面的元素要一步一步挪过去途中的每一步都要和其他元素做一次比较。这就好比排队的时候让最后一个人插到最前面他不喊借过而是一个一个问过去。数据越乱这个问过去的代价就越大。希尔排序的想法就是给插入排序装上弹跳能力。既然每次只能动一格太慢那就先让元素能一次跳好几格把大致位置摆对最后再用一次 gap 为 1 的完整插入排序收尾。此时数组已经基本有序收尾那趟就变成了插入排序最擅长的场景。1.2 分组的本质把一个大数组拆成若干条互不相干的小队列希尔排序的第一步操作叫按增量分组。设增量 gap 为 4那么下标 0、4、8、12…… 的元素归成一组下标 1、5、9、13…… 归成另一组以此类推。每一组内部各自做插入排序组与组之间完全独立互不干扰。这里有个特别容易被忽略的点分组不是物理上把数组切段而是按下标间隔抽取。很多人第一次看希尔排序代码脑子里会想成把数组分成前后几块分别排这是错的。下标 0、4、8 这三个元素在内存里隔着好几个元素它们被当成一队来处理靠的是下标运算而不是连续内存。理解了这一点后面代码里的j - gap这种写法就一点不奇怪了。为什么要这样抽因为这样做的好处是一次 gap 为 4 的排序过后每个元素都至少保证距离它的正确位置不超过若干个位置同时又不破坏组内有序这个性质。更关键的是每次缩小 gap 之后之前建立的部分有序性并不会被推翻。这就是增量序列必须递减的原因也是希尔排序能收敛的原因。如果 gap 从 4 跳到 9前面的工作就白做了。拿生活中的例子类比整理一屋子书先把书按大类粗略分堆大 gap再把每堆内部按作者排中 gap最后同一作者的书按年份细排gap1。每一轮都在上一轮的成果上细化而不是推倒重来。1.3 增量序列才是希尔排序真正的心脏希尔排序的框架——分组插入排序、逐渐缩小增量、最后 gap1 收尾——这部分是固定的换谁写都一样。真正决定性能的是那个增量序列怎么取。这是希尔排序和快排、归并最不一样的地方它的核心变量不在循环体里而在外面那个 gap 的生成规则上。拿最朴素的取法gap n / 2来说往下依次是 n/4、n/8…… 直到 1。这个序列的问题是当 gap 较大时比如 gap n/2实际上只有两个元素在同一组里比较做的工作量几乎可以忽略但之后的 gap n/4 仍然偏大真正有意义的比较集中在中后期。更糟的是这种折半序列在最坏情况下的时间复杂度依然是 O(n²)也就是说理论上它并没有比插入排序好到哪里去——只是平均表现好得多。而换一组设计得当的增量比如 Knuth 提出的 3h1 序列1, 4, 13, 40, 121……最坏情况可以压到 O(n^1.5)。Sedgewick 设计的那组更激进理论最坏能到 O(n^1.33) 量级。数字上的差别看着不大但放到十万级数据上就是实打实的秒级差距。所以我的态度一直很明确写希尔排序重点不是会不会写那三层循环而是能不能说清楚你用的是什么增量序列、为什么用它。面试里被追问你这段代码最坏复杂度多少答不出增量序列的人是答不上来的。1.4 什么时候该上希尔排序什么时候干脆别碰先说不该用的场景。数据量小到几十个元素直接插入排序就行希尔那套分组开销反而多余需要稳定排序的时候别用希尔排序是不稳定的这一点后面有专门的反例数据量上到百万级std::sort的 introsort 组合拳快排堆排插入排序不同版本实现有差异几乎肯定比你手写的希尔快没必要硬撑。那什么时候它合适我总结了三种情况。第一种是嵌入式或者资源受限环境。希尔排序的代码量极小不需要额外数组也不像快排那样有递归深度和栈空间的问题几十行代码就能落地编译出来体积也小。第二种是数据规模中等、但数据本身有一定局部有序性。希尔排序对这种输入特别敏感前面几趟就能把大部分元素归位后面的收尾几乎不费力气。第三种就是学习和面试场景。希尔排序是理解增量思想最好的载体它把分阶段降低问题规模这个思路演示得非常干净。很多人在学完之后再看 Timsort 里的 run 合并策略会有一种原来思路是一脉相承的感觉。2. 增量序列怎么选四种主流方案的构造与实测对比2.1 四套序列的生成代码与各自脾气第一套是希尔本人提出的折半序列也是几乎所有教材的第一版示例gap n / 2然后每次gap / 2直到gap变成 0。for (int gap n / 2; gap 0; gap / 2) { /* 组内插入排序 */ }这套写法最大的优点是简单、不用预处理、不用关心初始值。缺点是当 n 恰好是 2 的幂时表现会变差因为每一趟的 gap 都是偶数同一组里的元素下标奇偶性从头到尾没变过元素之间的比较容易集中在同一些下标上。第二套是 Hibbard 序列生成规则是2^k - 1即 1、3、7、15、31、63…… 这套序列的每个 gap 都是奇数而且相邻两个 gap 之间没有公因数能有效减少某些下标永远比不到一起的情况。理论最坏复杂度 O(n^1.5)。第三套是 Knuth 序列规则是h 3h 1得到 1、4、13、40、121、364…… 我的默认选择就是这一套。原因是它在实现上很干净用一个 while 循环预处理出不超过 n/3 的最大项然后往回推gap (gap - 1) / 3就行不需要维护一张预设表也不需要浮点运算。int gap 1; while (gap n / 3) { gap gap * 3 1; } for (; gap 0; gap (gap - 1) / 3) { /* 组内插入排序 */ }注意这里的gap n / 3和(gap - 1) / 3是配套的向前构造时用3h1向后回退时用(h-1)/3两者互为逆运算中间不会出现跳项。这一点如果写错序列会乱掉性能直接崩掉。第四套是 Sedgewick 序列用的是两个公式交替9 * 4^k - 9 * 2^k 1和4^k - 3 * 2^k 1合并后得到的序列是 1、5、19、41、109、209、505、929…… 这套序列的实测表现通常最好代价是生成逻辑要写个循环加奇偶判断或者干脆硬编码一张表。static const int SEDGEWICK[] {1, 5, 19, 41, 109, 209, 505, 929, 2161, 3905, 8929, 16001, 36289, 64769, 146305, 260609, 587521, 1045505};硬编码表的缺点是不通用超过表长就得回退到别的策略。我一般只在明确知道数据规模上限的场合用它。2.2 同机实测四套序列在十万级随机数据上的差距我在本机做过一组对比。测试方法是生成不同规模的随机整型数组元素范围 0 到 10^6每套序列各跑 20 次取平均编译开-O2关闭调试信息。下面这张表是相对趋势不是精确基准值不同机器、不同编译器版本跑出来的绝对值会有出入但排序关系基本稳定。数据规模n/2 折半HibbardKnuthSedgewick10^4完全随机基准 1.00约 0.88约 0.85约 0.8310^5完全随机基准 1.00约 0.82约 0.79约 0.7610^5近乎有序乱序率 5%基准 1.00约 0.55约 0.52约 0.5010^5逆序基准 1.00约 0.68约 0.66约 0.64说几个从数据里读出来的结论。差距最明显的地方是近乎有序的输入。这时候四套序列之间的相对差距被放大Sedgewick 能比折半快将近一倍。原因不难想数据本来就有序好序列能让第一趟就完成大量归位把工作量压到最小。差距最小的场景是逆序输入。逆序时每组元素都要搬到另一头任何序列都省不下来这部分搬移开销所以大家的表现被拉平了。n 从 10^4 涨到 10^5各序列之间的相对比例变化不大说明这几套序列的复杂度量级在同一档差异主要来自常数项和具体数据分布。这里必须强调一句这类微基准测试非常容易测出误导性结论。缓存效应、内存带宽、随机数生成器的质量都会干扰结果。我做这组对比时用的是同一份预先生成好的数组副本避免随机数生成本身耗时被算进去。如果你自己复现务必把数组生成放在计时区间之外。2.3 选型建议以及一个被忽略的细节我的实操结论是默认用 Knuth 序列。理由有三个。它不需要额外存储不像 Sedgewick 那样要维护表或复杂生成逻辑它的性能已经能覆盖绝大多数场景和 Sedgewick 的差距在小数据量下几乎看不出来它的构造和回退互为逆运算代码短出错概率低。如果你明确知道数据规模的上限并且追求极致那就用 Sedgewick 的硬编码表配合一个 fallback当数组长度超过表里最大项时从表尾往前找第一个不超过n/3的项开始。最后说一个容易被忽略的细节增量序列的初始值不应该超过 n 本身太多。如果初始 gap 比 n 还大所有元素各成一组,这一趟就是空转纯浪费时间。有些实现在生成序列时没做上界判断直接算到几百上千然后第一趟全部空跑。Knuth 序列用while (gap n / 3)就是为了避开这个问题——它保证初始 gap 落在 n/3 到 n 之间第一趟就能真正做有效工作。3. C/C 手写实现全流程从三十行到可复用版本3.1 最朴素的 C 版本与逐行拆解先上第一版这是所有教材都会给的样子也是我建议你背下来的版本。#include stdio.h void shell_sort(int arr[], int n) { for (int gap n / 2; gap 0; gap / 2) { for (int i gap; i n; i) { int temp arr[i]; int j i; while (j gap arr[j - gap] temp) { arr[j] arr[j - gap]; j - gap; } arr[j] temp; } } }外层gap循环控制增量序列从 n/2 开始折半。中间这层i循环是整套代码的关键它从gap开始遍历到n-1每遇到一个下标就把它插入到以它为最后一个元素的那一组的正确位置上。这里解释一下为什么i从gap开始而不是从 0 开始。当下标小于 gap 时这些元素都是各自组里的第一个元素一个只有一个元素的序列天然有序不需要处理。从gap开始正好是每一组的第二个元素这才是需要做插入的起点。这个起始点的选择看起来只是省了几个循环但它保证了下标运算i - gap永不为负省掉了一次边界检查。内层while是标准插入排序的搬移逻辑只是把步长 1 换成了gap。temp保存待插入元素j一路往回跳凡是比自己大的元素统统后移一格这里的一格是 gap 的距离直到找到合适位置或者跳出数组左边界。while里的条件顺序很重要j gap arr[j - gap] temp。必须把边界判断写在前面。C 语言的有短路特性如果j gap为假后面的arr[j - gap]根本不会被求值。如果写反了当j小于gap时就会访问arr[负数]这是典型的越界读小数据下可能不崩大数据下就是随机段错误。3.2 Knuth 序列改造与循环边界的推导把折半序列换成 Knuth 序列改动集中在最外层循环void shell_sort_knuth(int arr[], int n) { if (n 2) return; int gap 1; while (gap n / 3) { gap gap * 3 1; } for (; gap 0; gap (gap - 1) / 3) { for (int i gap; i n; i) { int temp arr[i]; int j i; while (j gap arr[j - gap] temp) { arr[j] arr[j - gap]; j - gap; } arr[j] temp; } } }推导一下gap n / 3这个条件是怎么来的。我们希望初始 gap 尽可能大但不能大到让第一趟变成空转。如果 gap 取到 n那么每组只有一个元素完全没意义。理想的上界是让每组至少有两个元素也就是n / gap 2即gap n / 2。Knuth 序列的项是 1、4、13、40、121…… 每一项约等于前一项的三倍所以当gap逼近 n/3 时下一个3*gap1就会超过 n/2。用n/3作为循环继续条件恰好让最终的 gap 落在 [n/3, n/2] 这个区间里。回退时的(gap - 1) / 3同样要推一下。设当前 gap 是3h 1那么(3h 1 - 1) / 3 h正好回到上一项。整数除法在这里是安全的因为gap - 1一定能被 3 整除。但如果序列构造时用了别的系数比如4h 1回退就变成(gap - 1) / 4一旦某一步算错整个序列就断了会退化成一堆无意义的 gap 值。我见过一种错误写法是把回退写成gap gap / 3看起来差不多实际上会丢失序列中的项。以 40 为例40 / 3 13正好对上但以 4 为例4 / 3 1也对得上。问题出在那些不能整除的情况比如从 13 推13 / 3 4也对。这个写法在很多情况下能跑出正确结果但它依赖整数除法的向下取整恰好和(h-1)/3一致属于碰巧对不该当成正确写法用。另外加了if (n 2) return;这个前置判断。n 为 0 或 1 时数组本来就有序直接返回能省掉不必要的循环。这个小判断在实际项目里值得保留因为排序函数经常被泛型容器调用空容器是常见输入。3.3 模板化改造与 C 迭代器版本C 版本够用但如果你在写 C 项目用一个模板版本会更顺手至少能直接吃std::vector。#include vector #include functional #include iterator template typename RandomIt, typename Compare void shell_sort(RandomIt first, RandomIt last, Compare comp) { auto n last - first; if (n 2) return; using Diff typename std::iterator_traitsRandomIt::difference_type; Diff gap 1; while (gap n / 3) { gap gap * 3 1; } for (; gap 0; gap (gap - 1) / 3) { for (Diff i gap; i n; i) { auto temp *(first i); Diff j i; while (j gap comp(temp, *(first j - gap))) { *(first j) *(first j - gap); j - gap; } *(first j) temp; } } } template typename RandomIt void shell_sort(RandomIt first, RandomIt last) { shell_sort(first, last, std::less()); }几点说明。用RandomIt而不是T*是为了同时支持原生数组的指针和std::vector::iterator。用std::iterator_traits取difference_type而不是硬写int是为了处理超大容器避免int溢出。比较器参数comp(temp, *(first j - gap))的参数顺序要留意它的语义是temp 应该排在 j-gap 位置元素的前面。如果你传std::greater()得到的会是降序排列。顺序写反了会得到一个反过来的结果而且不会报错只会默默排错。这是模板代码最坑的地方之一编译器帮不了你。还有一个实际工程里的坑模板函数通常要写在头文件里。如果把定义放在.cpp里另一个翻译单元调用时会链接失败报一堆undefined reference。原因是模板只有在实例化时才生成代码而编译器在编译调用方的时候看不到定义没法实例化。这个坑每年都有无数人踩尤其是从 C 转 C 的人。3.4 几个能白捡性能的微优化说几个我实测有效的小改动不改算法结构纯赚性能。第一个把arr[j - gap] temp里对arr的重复下标运算提前算出来。现代编译器基本能自动优化掉但在-O0调试构建下手动提一下会有肉眼可见的差别尤其是调试大数据量的时候。第二个用int存temp而不是每次都从数组里读。这个原始版本已经做到了写的时候千万别改成swap版本。用 swap 交换相邻元素虽然代码看着对称但每次交换是三次内存写而搬移法是每次一个写最后再补一次效率差不少。第三个如果数据是整型且范围不大可以用哨兵元素省掉j gap这个边界判断。做法是在每组最前面插一个极小值让内层循环一定能被哨兵拦住。代价是需要额外的数组空间或者预处理一般不值得除非你对性能有极端要求。我一般不加这一层因为带来的复杂度超过收益而且容易写出越界 bug。第四个把外层循环的gap / 2换成gap 1在整数上等价但现代编译器早就自己做了这个优化写不写没区别。写 1反而会让人误以为你在做什么特殊处理不如老实用除法可读性更重要。4. 在 VSCode 里把希尔排序一趟一趟看明白4.1 环境准备与调试配置要点光看代码容易看懂但希尔排序的循环嵌套比插入排序多一层中间变量gap、i、j之间的关系不亲手跟几趟很难形成直觉。所以我强烈建议在编辑器里把它跑起来用断点和单步看每一趟的变化。用 VSCode 写 C/C 的话需要装微软官方的 C/C 扩展。装完之后如果遇到智能提示失效、结构体成员补全不出来先检查这几件事工作区的c_cpp_properties.json里includePath和compilerPath是否指向你本机真实的编译器打开的文件是否在browse.path覆盖的目录里以及右下角的状态栏显示的是不是正确的配置名称。多套配置比如 MinGW 和 MSVC 并存切换时容易切到错的那个症状就是头文件全红。调试配置我一般用这两份文件。编译任务{ version: 2.0.0, tasks: [ { label: build-debug, type: shell, command: g, args: [ -g, -O0, -Wall, -Wextra, -stdc17, ${file}, -o, ${workspaceFolder}/build/main ], group: { kind: build, isDefault: true }, problemMatcher: [$gcc] } ] }启动配置{ version: 0.2.0, configurations: [ { name: gdb 调试当前文件, type: cppdbg, request: launch, program: ${workspaceFolder}/build/main, args: [], stopAtEntry: false, cwd: ${workspaceFolder}, environment: [], externalConsole: false, MIMode: gdb, preLaunchTask: build-debug, setupCommands: [ { description: 启用 gdb 整齐打印, text: -enable-pretty-printing, ignoreFailures: true } ] } ] }-O0是必须的。开了优化之后编译器会把循环变量优化进寄存器gap、j这些变量在调试器里会显示成已被优化掉或者显示错误的值根本没法跟。我吃过这个亏明明打断点了看变量值却是上一次迭代的残留排查了半天才发现是-O2导致的。4.2 断点该打在哪几个位置不要在外层gap循环上打断点那样你每按一次继续只能看到一个 gap 值跟不出组内发生的事。我习惯打三个断点。第一个打在for (int i gap; i n; i)这一行。每次命中说明开始处理一个新的元素此时观察gap的值能清楚知道现在处于哪一趟。第二个打在while (j gap arr[j - gap] temp)这一行。命中说明当前元素需要往前搬观察j和j - gap的值看看到底跨了几格。第三个打在arr[j] temp;这一行。这是插入完成的时刻此时看数组前几个元素能直观感受到每一趟之后数组变得更有序。配合监视窗口把gap、i、j、temp四个表达式加进去数组整体用arr[0]10这种形式看前十个元素gdb 语法监视表达式里直接写。一趟跟下来希尔排序在做什么就非常清楚了。我的经验是跟着 n16 的数组走一遍完整流程就够形成直觉。数组越大断点命中次数指数级增长跟到后面会失去耐心。建议第一次用固定的小数组比如{9, 1, 5, 3, 7, 2, 8, 4, 6, 0}手动跑。4.3 加一段打印代码把每一趟的状态打出来调试器只能一次看一个点。如果要看全局变化趋势加打印更高效。写一个只在调试构建里生效的打印块#ifdef SHELL_DEBUG #include cstdio #define DUMP_ARR(a, n) \ do { \ for (int _k 0; _k (n); _k) \ std::printf(%4d, (a)[_k]); \ std::printf(\n); \ } while (0) #else #define DUMP_ARR(a, n) ((void)0) #endif然后在 gap 循环的开头加一句DUMP_ARR(arr, n);。用-DSHELL_DEBUG编译时就能看到每一趟增量开始前的数组状态不定义这个宏时打印代码完全被剔除没有任何运行时开销。用一个长度 10 的数组实际跑一下输出大概长这样初始: 9 1 5 3 7 2 8 4 6 0 gap4: 7 1 5 3 9 2 8 4 6 0 gap2: 5 1 7 2 6 0 8 3 9 4 gap1: 0 1 2 3 4 5 6 7 8 9看第一行到第二行gap4 的时候下标 0 和 4 的元素 9 和 7 之间做了比较7 被搬到了前面。第二行到第三行gap2 时分组变密集了更多的元素归位。最后 gap1 时数组已经相当有序一趟插入排序就收尾了。这就是希尔排序最直观的样子每一趟都在让数组变得更像有序最后一趟只是补个刀。把这段打印跑上三五遍比看十遍代码管用。5. 踩坑记录与问题速查表5.1 我实际踩过的五个坑第一个坑内层while条件写反导致的越界。前面提过j gap和arr[j - gap] temp的顺序不能颠倒。我当年写反过一次在小数组上跑得好好的一上大数据就在完全随机的位置段错误。定位花了很久因为崩溃点和逻辑错误点看起来没关系。后来养成习惯涉及下标运算的条件一律把边界判断放最左。第二个坑处理 n 为 0 或 1 时的空循环。折半序列版本在 n1 时gap 1/2 0外层循环直接不执行看起来是安全的。但换成 Knuth 序列之后gap 1然后while (gap n / 3)中n/3 0条件为假gap 保持 1外层循环进得去内层for (int i 1; i 1; i)不执行也是安全的。但如果你在模板版本里加了别的预处理逻辑就未必了。加一句if (n 2) return;是最省事的保险。第三个坑把gap递减写成gap / 3而不是(gap - 1) / 3。前面分析过这在很多情况下碰巧正确但一旦序列构造用了不同的系数就会出错。我在一次代码评审里看到这个写法测了几组数据都是对的最后还是让改了——理由不是它现在错而是它经不起改动。第四个坑模板定义放在.cpp里。这个坑我踩了不止一次。给一个模板排序函数写单测测试代码在另一个.cpp编译链接直接报一堆undefined reference to void shell_sort...。解决方式就是老老实实把模板定义挪到头文件或者在同文件里显式实例化template void shell_sortint*(int*, int*);。前者更通用。第五个坑用-O2调试。症状是断点位置和实际执行位置对不上变量值显示成一堆寄存器名或者随机数。这不是代码问题是构建配置问题。调试用-O0 -g发布用-O2两者分开别混着来。5.2 常见问题速查表现象可能原因排查方向小数据正常大数据随机崩溃内层条件顺序写反出现负数下标检查while条件j gap必须在左数组结果正确但末尾几个元素乱外层 gap 循环退出条件写错确认 gap 递减到 1 才停不能提前跳出排序后元素丢失或重复搬移逻辑里漏了最后的arr[j] temp检查while之后是否补上赋值性能比插入排序还差初始 gap 超过 n第一趟空转检查序列构造的上界条件调试时变量显示已被优化编译开了优化改用-O0 -g重新编译模板版本链接报 undefined reference模板定义在.cpp中把定义移到头文件或显式实例化降序排序结果不对比较器参数顺序反了检查comp的调用参数顺序5.3 怎么验证复杂度怎么验证不稳定性验证时间复杂度最直接的方法是计时加拟合。把 n 取成 10^4、2×10^4、4×10^4、8×10^4 这几档每档跑多次取平均然后看耗时随 n 增长的倍数。如果 n 翻倍耗时大约变成 2.8 倍左右说明实际复杂度在 n^1.5 附近和 Knuth 序列的理论值对得上。如果明显超过 3.5 倍那就要反思是不是序列取错了。验证不稳定性需要一个专门的例子。前面推导过的这组数据可以用int a[] {3, 5, 1, 3}; // 两个 3 分别记为 3a下标 0和 3b下标 3n4gap 从 2 开始。第一趟 gap2组 1 是下标 0 和 2 的3a和1组 2 是下标 1 和 3 的5和3b。处理完之后数组变成{1, 3b, 3a, 5}注意此时3b跑到了3a前面。第二趟 gap1 是标准插入排序两个相等的 3 之间的相对顺序不会再变最终结果就是3b在前。如果要判断一个排序函数是否稳定不用看代码直接跑这个数组看输出里两个 3 的原始下标有没有反转即可。前提是你在代码里能区分它们一般做法是把值改成能区分的形式或者打印下标。这个例子说明希尔排序不适合任何要求相等元素保持原始顺序的场景。典型受影响的是多关键字排序先按姓名排再按部门排如果第二轮用的是希尔排序第一轮排好的姓名顺序可能被打乱。要稳定就得换成归并排序或者稳定版的插入排序。我个人在实际项目里的做法是把排序函数按需求分类放好注明哪些是稳定的哪些不是用的时候就按名字挑不靠记忆。这个习惯帮我省过好几次返工。希尔排序在这份清单里的定位是中等规模、内存敏感、不需要稳定性的场合默认实现用 Knuth 序列追求极致时换 Sedgewick 并准备好兜底表。至于调试把每一趟的数组打印出来的那一招是我觉得性价比最高的学习手段花十分钟加打印比读两小时代码管用。