1. 从直接插入排序的两头好使说起很多人学习排序第一个认真研究的算法是冒泡或直接插入。直接插入排序的代码简单到让人怀疑它是不是有点笨每次把一个元素往前插前面的序列已经有序只需要找到合适的位置。但真正跑数据的时候这台笨办法有个非常鲜明的性格——数据基本有序时快得离谱数据完全乱序时慢得让人抓狂。我最早在C语言课上写希尔排序时老师并没有直接抛出它的定义而是先让我们用直接插入排序去排一个10万元素的逆序数组。那次实验让我印象极深冒泡排序跑了十几秒直接插入排序也差不多而一旦换成希尔排序几乎是眨眼的功夫就结束了。当时我甚至怀疑自己写的排序是不是根本没执行。后来回头翻书才知道希尔排序本质上是对直接插入排序的增量改进版它干的事情很简单先跳过一段距离去比较和交换让数组在宏观上先变得大致有序最后再退化成普通的直接插入排序收尾。希尔排序在C语言实现中的位置很特殊。它不像快排那样依赖递归和函数调用栈也不像归并排序那样需要额外的辅助数组。它的全部逻辑就是三层循环加一个临时变量空间复杂度是O(1)代码量也就二十行出头。但也正因为代码短很多初学者容易产生这玩意儿不就是插排加了个gap吗的错觉从而忽略了它真正的设计思想——也就是增量序列的选取。这篇博文我想完整地把希尔排序讲透从它为什么快、增量怎么选、C语言怎么写到稳定性、复杂度分析再到实际工程中的取舍一次说清楚。2. 希尔排序的分组与增量设计gap是怎么动的2.1 希尔排序到底做了什么事直接插入排序之所以慢是因为每次只能把元素往后挪一格。比如说数组里有10000个元素最小的那个偏偏在最后一位那插入排序要从倒数第二位一路比较、一路挪动几乎遍历完整个数组才能让它归位。元素越多这种一格一格挪的成本就越高。希尔排序的思路很直白既然一次挪一格太慢那我能不能先一次挪好几格具体做法是把数组按某个间隔gap分成若干组对每一组分别做插入排序。举个例子gap等于5的时候索引0、5、10、15这些是同一组索引1、6、11、16是同一组索引2、7、12、17又是一组。每个组内部的元素比较时直接跨越gap个位置大的元素可以一次性往后跳好几步小的元素也能一次性往前跳好几步。这样经过几趟宏观排序整个数组会变得非常接近有序最后再用gap1也就是普通插入排序收尾这时需要移动的元素已经很少了。这个过程有个专门的说法叫递减增量排序。gap从大变小每一步都在为下一步铺路。最后一次gap1的插入排序之所以能跑得飞快正是因为它面对的数组里倒数的乱序已经不多了。简单说希尔排序就是用前面几趟的粗调换最后一趟精调的轻松。2.2 增量序列的选择不是随便分组的gap怎么选是整个希尔排序里最核心也最有意思的问题。最朴素的写法是gap n / 2然后每次gap / 2一直缩到1。这种写法也叫Shell增量是希尔本人最早提出的代码简单好记但它的最坏时间复杂度能达到O(n²)理论上并不比直接插入排序好太多——只不过在实际数据中往往远好于这个最坏界。还有两种常见的改进方案。一种是Hibbard增量gap取值为1, 3, 7, 15, 31……也就是2^k - 1它的最坏时间复杂度可以优化到O(n^(3/2))。另一种是Sedgewick增量gap序列形如1, 5, 19, 41, 109……最坏复杂度大概在O(n^(4/3))平均也能到O(n^(7/6))。在实际代码里我见过不少工程实现喜欢用gap gap / 3 1这种写法虽然它不完全等同于Sedgewick增量但实测表现往往比简单n/2折半要稳定尤其在中大规模数据下能明显少跑几趟。下表整理了常见增量序列和它们的性质方便对比增量序列递推方式最坏时间复杂度特点Shell增量折半gap n / 2每次除以2O(n²)实现最简单适合教学Hibbard增量(2^k) - 1O(n^(3/2))跳变距离更远Knuth增量(3^k - 1) / 2约O(n^(3/2))工程中常见折中Sedgewick增量混合序列约O(n^(4/3))理论表现更好序列复杂需要注意的是希尔排序的时间复杂度到现在都还没有一个统一结论因为它的复杂度严重依赖增量序列的选择和具体数据的分布。这一点和快排、归并的严谨复杂度分析完全不同也是它理论上比较吃亏的地方。但换个角度看也正是这种不确定性让增量序列的研究变成了一个很有趣的算法设计话题。2.3 为什么gap最后必须等于1很多人写希尔排序时会有个疑问为什么前面几趟拍完还不够最后一定要再来一次gap1的插入排序原因很简单因为前面的分组排序只保证了组内有序组与组之间并没有完全的全局顺序。比如gap5跑完后索引0到4这前几个元素分别来自不同的组它们之间的相对顺序可能是乱的。只有gap1这趟把整个数组当成一个组做标准插入排序才能保证整体有序。这个最后必须gap1的约束也是判断一个希尔排序实现是否正确的基本检查项。有些代码为了追求速度在最后一个gap不是1的序列上跑完就直接返回那结果一定是错的。我调试希尔排序时有个固定的习惯写完代码后先用一个固定数组跑一遍在循环里打印每一趟gap结束后的数组状态确认最后一次gap确实是1并且数组最终按升序排列才算是真正过关。3. C语言实现核心代码逐行拆解3.1 一套干净可跑的完整实现直接上一份我常用的C语言实现这段代码可以在任何标准C环境下编译运行不需要额外依赖#include stdio.h void shellSort(int arr[], int n) { // 外层循环控制gap从大到小衰减最后必须衰减到1 for (int gap n / 2; gap 0; gap / 2) { // 中层循环从gap位置开始遍历到数组末尾 // 之所以从gap开始是因为每个分组内索引0处是已排好的起点 for (int i gap; i n; i) { int temp arr[i]; int j i; // 内层循环在组内做插入排序往前找合适的位置 // 每次比较跨过gap个位置 while (j - gap 0 arr[j - gap] temp) { arr[j] arr[j - gap]; j - gap; } arr[j] temp; } } } void printArray(int arr[], int n) { for (int i 0; i n; i) { printf(%d , arr[i]); } printf(\n); } int main() { int arr[] {9, 8, 7, 6, 5, 4, 3, 2, 1, 0}; int n sizeof(arr) / sizeof(arr[0]); printf(原始数组\n); printArray(arr, n); shellSort(arr, n); printf(排序结果\n); printArray(arr, n); return 0; }这段代码最核心的地方在于中层循环的起点是gap而不是0或gap1。初学的时候我踩过一个坑以为要对每个分组分别做两层循环于是写出了四个循环嵌套的版本逻辑复杂度成倍上升。实际上从i gap开始向后逐个遍历天然就把所有分组都覆盖到了。因为每个元素在它所属分组里的插入排序只需要和前面间隔gap的元素比较而前面的元素要么已经有序要么在本轮之前的迭代中已经被处理过了。这个跨组遍历的技巧是理解希尔排序C语言实现的关键也是让代码保持简洁的首选写法。3.2 如果想看清楚每一趟发生了什么纯排序代码只能看到最终结果不方便理解过程。调试或者写文档的时候我习惯在每趟gap排序结束后打印一次数组状态。借助printf可以看到gap从大到小的过程中数组是如何逐步逼近有序的void shellSortWithTrace(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 0 arr[j - gap] temp) { arr[j] arr[j - gap]; j - gap; } arr[j] temp; } printf(gap %d, gap); printArray(arr, n); } }加上这一小段输出之后拿一个十元素数组跑一遍基本一眼就能看清希尔排序的粗调精调过程。我强烈建议初学者亲手把这个带输出的版本跑一遍比看任何静态的示意图都有用。3.3 关于gap初始化的一点细节上面代码里gap的初始值是n / 2这个写法简单但如果你用gap / 2来递减就会遇到一个问题当n2时gap初始是1直接进入插入排序没问题当n4时gap序列是2、1也没问题但当n6时gap序列是3、1跳过了gap2这样的跳跃会不会影响正确性答案是不会只要最后能到达gap1任何递减序列都不会影响正确性只影响效率。不过在实际工程中我更喜欢用gap gap / 3 1这种写法。它同样是从n/3起步但衰减速度更平缓很多数据分布下需要跑的趟数略多但每趟的精细化程度更高整体耗时反而经常更短。这个选择没有绝对的优劣建议在不同数据量下自己跑一遍对比。排序算法的学习过程中最忌讳的就是把某种写法当成标准答案gap选取本身就是个调参的过程。4. 用一组数据手工跑一遍看希尔排序到底做了什么4.1 从完全逆序的十元素数组开始光讲理论总是差的我拿了平时讲课最喜欢用的一组数据{9, 8, 7, 6, 5, 4, 3, 2, 1, 0}。这是一个完全逆序的十元素数组最能体现希尔排序的价值因为这种情况下直接插入排序需要做45次交换而希尔排序可以大幅减少交换次数。n 10如果用折半增量gap序列就是5、2、1也就是一共跑三趟。第一趟gap 5数组被分成5组每组2个元素组1索引0、5对应9、4 - 排序后4、9组2索引1、6对应8、3 - 排序后3、8组3索引2、7对应7、2 - 排序后2、7组4索引3、8对应6、1 - 排序后1、6组5索引4、9对应5、0 - 排序后0、5这一趟结束后数组变成{4, 3, 2, 1, 0, 9, 8, 7, 6, 5}。可以看到原来全部聚集在后面的小元素一下子被提到了前半部分这就是gap带来的远距离搬运效果。第二趟gap 2数组被分成2组组1偶数索引4、2、0、8、6 - 插入排序后0、2、4、6、8组2奇数索引3、1、9、7、5 - 插入排序后1、3、5、7、9合并回完整数组时按索引交错填入索引0是0索引1是1索引2是2索引3是3索引4是4索引5是6索引6是5索引7是7索引8是8索引9是9最终得到{0, 1, 2, 3, 4, 6, 5, 7, 8, 9}。注意这里有意思的地方经过gap2的排序数组已经非常接近有序只剩下6和5这一对逆序。第三趟gap1做普通插入排序时只需要交换一次就把数组变成了{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}。4.2 这组数据说明了什么对比一下三种算法在这个数组上的表现。冒泡排序和直接插入排序处理完全逆序的十元素数组几乎每个元素都要往后移动很多次而希尔排序用三趟、一共不到二十次的比较和移动就完成了整体排序。这背后的本质是希尔排序把远距离移动提前做了最后一趟插入排序只需要做微调。如果你把同样的数组放大到一万元素差距会更明显。直接插入排序在最坏情况下的移动次数是n(n-1)/2也就是将近5000万次希尔排序在实际数据中通常能把这个量级压低到百万次以内。这也是为什么很多老工程师在数据量不算特别大的场景下宁可写希尔排序也不愿意用快排的原因——代码短、栈不深、常数小性能完全够用。4.3 亲手验证代码的三种途径如果你想验证自己写的希尔排序是否正确我常用的办法有三个用这个小数组跑一遍和上面推导的结果逐一比对发现不一致就说明代码逻辑有误。写一个isSorted函数检查排序结果再用随机数生成器产生各种规模的数组批量验证。和系统自带的qsort跑同样的数据对比排序结果但注意qsort是快排实现比的是最终正确性而不是性能。这三个方法中随机数批量验证最容易发现边界问题。比如数组长度为0、1、2时希尔排序能不能正常结束gap会不会出现除以零的情况这些边界场景用固定用例很难覆盖到但随机测试一跑就全暴露了。5. 稳定性、时间复杂度和那个没完全解决的问题5.1 希尔排序为什么是不稳定的很多资料会告诉你希尔排序不稳定但没说清楚为什么。要理解这一点得先搞清楚排序算法里稳定的含义两个值相等的元素排序后它们的相对位置不能变。直接插入排序为什么稳定因为它只在遇到严格大于当前元素的值时才移动相等时不动。冒泡排序等也一样都是通过等于不交换来保证稳定。希尔排序的问题出在分组上。举个例子看数组{3a, 2, 1, 3b, 2}两个3分别是3a和3b原数组中3a在3b前面。gap2的时候第一组包含索引0、2、43a、1、2第二组包含索引1、32、3b。第一组排序后变成1、2、3a第二组排序后变成2、3b合并后数组是{1, 2, 2, 3b, 3a}。这时候你会发现3b跑到了3a前面两个相等的元素相对位置被翻转了。这就是希尔排序不稳定的根源——元素会跨组跳跃移动而一次跨组跳跃就可能越过某个和它相等的元素。这个不稳定性在实际工程中的意义是如果你需要对多个字段依次排序比如先按年龄排再按姓名排那么第二次排序必须是一个稳定排序否则第一次排序的结果会被打乱。希尔排序在这种场景下就不适用你会优先选择归并排序这类稳定算法。5.2 空间复杂度与时间复杂度空间复杂度方面希尔排序只用了几个整型临时变量是严格的O(1)原地排序不需要额外数组不递归不占用调用栈。这一点在单片机、嵌入式设备这些内存紧张的环境里是很大的优势。时间复杂度就没那么干脆了。直接插入排序的复杂度很明确最好O(n)最坏O(n²)。希尔排序取决于增量序列以及数据本身的分布。为了有个直观认识我把不同增量序列下的最坏情况复杂度列出来了增量序列最坏时间复杂度折半递减ShellO(n²)Hibbard增量O(n^(3/2))Knuth增量约O(n^(3/2))Sedgewick增量约O(n^(4/3))更玄学的是希尔排序的平均时间复杂度至今没有被严格证明出统一公式。对不同gap序列、不同数据分布学术界给出的结论都不一样。这也是我教学时特别喜欢提的一个点它不像快排那样有一个可以精确推导的平均O(n log n)这反而让希尔排序蒙上了一层经验主义的色彩。更准确地说希尔排序的性能在很大程度上取决于程序员对gap序列的取舍而这种取舍往往来自实测而不是理论推导。5.3 一个有趣的算法开放问题希尔排序的复杂度分析在算法领域是个出了名的老大难。Donald Knuth在他的《计算机程序设计艺术》里讨论过各种gap序列的复杂度问题但时至今日如何找到任意n下最优的增量序列依然没有一个公认的最终答案。相比快排、堆排这类复杂度已经被彻底研究的算法希尔排序在这方面显得有些粗糙。但这恰恰也是它的魅力所在。写快排的时候代码几乎每个细节都被前人优化到了极致留给你的发挥空间很少而写希尔排序的时候你可以自由选择gap序列、调整递减策略甚至能针对特定数据分布设计出自己的增量方案。作为一个练手项目希尔排序在算法优化方面的可玩性远高于其他排序。6. 实际工程中的取舍它和冒泡、插入、快排比到底差在哪6.1 在不同数据规模下的实测感受我在电脑上做过一个简单的对比实验随机生成10000个整数分别用冒泡排序、直接插入排序、希尔排序和快排去排。结果很典型冒泡和直接插入大概耗时几百毫秒希尔排序在个位数毫秒级别快排在两三毫秒左右。数据量升到100万时快排优势更明显但希尔排序依然可以在一秒内完成而冒泡和直接插入基本已经可以放弃治疗了。这个结果说明了希尔排序的定位它处在简单排序和高级排序之间的中间地带。比冒泡和插入快一个量级比快排和归并慢一些但它不需要递归、不需要额外内存、代码量极小这三个特性很多时候足以弥补速度上的差距。6.2 什么时候适合用希尔排序根据我的实际经验希尔排序比较适合这几类场景数据量在几千到几十万之间且对排序速度有要求但又不是极端苛刻。运行环境的内存很紧张不能用归并的辅助数组或快排的递归栈。嵌入式环境下编译器对递归支持有限或者干脆禁用了递归。数据本身已经有部分有序此时希尔排序的预排序效果会非常明显。反过来说如果你的数据量到了千万级别或者对最坏情况时间有硬性要求比如实时系统里不能出现某个输入导致时间暴增那希尔排序可能不是最优解这时快排的优化版本或堆排会更可靠。6.3 一个折中的工程写法如果只让我在生产代码里选一种不依赖系统库的排序实现我大概率会写这样一个函数当n小于某个阈值时用直接插入排序否则用希尔排序先预排序再考虑是否切到插入排序收尾。这个思路在数据基本有序、但偶尔有大乱序的场景里特别有效。void hybridSort(int arr[], int n) { if (n 16) { // 小数组直接用插入排序 for (int i 1; i n; i) { int temp arr[i], j i - 1; while (j 0 arr[j] temp) { arr[j 1] arr[j]; j--; } arr[j 1] temp; } } else { // 大数组先用希尔排序做宏观调整 for (int gap n / 3 1; gap 0; gap gap / 3) { for (int i gap; i n; i) { int temp arr[i], j i; while (j - gap 0 arr[j - gap] temp) { arr[j] arr[j - gap]; j - gap; } arr[j] temp; } } } }为什么要加这个16的阈值因为插入排序在数据规模很小时有极小的常数因子甚至比快排还快而希尔排序的gap序列在n小于16时优势发挥不出来。这个阈值不一定必须是168、32也都可以看实际场景调整。这种混合排序的思路在标准库的sort实现中也很常见本质上是不同算法在不同数据规模下的分工协作。7. 为什么现在还要学希尔排序在很多教材里希尔排序被放在插入排序后面篇幅不大代码也短看起来像个过渡角色。但在实际的学习路径中希尔排序的价值远远不止多会一种排序这么简单。第一它是理解增量思想的最佳入门材料。所谓增量思想是先通过大步长降低问题的复杂度再逐步缩小步长精化结果。这种思想在后续学习二分搜索、倍增法、稀疏表等算法时会不断遇到。希尔排序用最简单直观的形式让你体验到了分阶段逼近的威力。第二它是最适合做算法正确性验证练手的题目。因为希尔排序涉及到多重循环、gap边界、组内插入排序等多个容易出错的地方写完之后你不得不去思考各种边界条件。这个过程对于锻炼程序思维非常有帮助。很多计算机二级的C语言考试以及面试中的手写算法题也都喜欢拿排序来考察候选人的基本功希尔排序出现频率相当高。第三从C语言学习的角度看希尔排序是个绝佳的综合练习素材。它需要你熟练使用数组、循环嵌套、函数封装还能顺带练到指针传参、动态数组分配等知识点。相比单纯的打印菱形求水仙花数这类题目排序算法更贴近真实编程场景。如果把希尔排序扩展成支持任意数据类型的通用版本你还能练到函数指针和泛型编程的思想。最后我再分享一个写希尔排序时的个人习惯永远在循环开头打印一次当前数组状态。这个习惯是在一次调试中养成的那次我写的gap序列在某个n下跳过了1导致排序结果时对时错。加了打印之后一眼就发现了问题。如果你正在学习或复习希尔排序我建议你也把这一步加上哪怕最终提交的版本里不会保留这些打印语句调试过程中的每一行输出都会帮你加深对gap变化的理解。