学排序算法的时候很多人第一反应是冒泡、选择、插入再往上就是快排、归并。夹在中间位置上的希尔排序挺尴尬——说简单吧它比冒泡复杂一截说难吧它又没有快排那种“分治递归”的架子。但我在实际写C语言代码的过程中反而觉得希尔排序是最值得手写一遍的排序算法之一。它实现不复杂却把“先宏观粗略有序再微观局部精细”的思路体现得特别清晰而且在数据量不大不小的场景下性能相当能打。这篇文章我会从头拆一遍希尔排序的C语言实现为什么用间隔分组、gap到底怎么选、代码怎么写不容易踩坑、以及它和插入排序、快速排序放在一起实测时差距有多大。不管你是刚接触C语言的学生还是在准备计算机二级、数据结构期末考都可以从里面拿到能直接用的东西。开始之前多说一句这里所有代码我都是在 VSCode 配好 C/C 环境后跑的环境不同结果会有细微差别但算法逻辑完全一致。1. 先搞清楚希尔排序到底在解决什么问题1.1 插入排序的短板数据越乱搬移越频繁要说希尔排序必须先说插入排序。插入排序的思路很直观把数组分成“已排序区”和“未处理区”每次从未处理区拿一个元素从右往左在已排序区里找到合适位置插进去。它在小规模数据、或者数据已经基本有序的时候非常快很多 C 语言教材和翁恺老师的练习题里都用它当入门排序。但插入排序有个致命短板如果数据是完全逆序的时间复杂度会稳稳落到 O(n²)。举个例子数组是 [5,4,3,2,1]插入排序需要把4往前挪1位3往前挪2位2往前挪3位1往前挪4位。元素每往前移动一步都要经过一次“比较赋值”。数据规模到10万的时候这种就地搬移的次数会膨胀到几千万次跑起来非常慢。问题的根源在于插入排序每次只能把一个元素往前移动一格。对于乱序严重的数组一个很小的元素可能藏在数组末尾它要“走”到正确位置必须和前面所有比它大的元素逐一交换效率被拖垮。1.2 希尔排序的核心思想先让数据“宏观有序”希尔排序的改进思路很有意思既然插入排序在“基本有序”时效率高那能不能先让数组变得基本有序再做最后一遍插入排序怎么做到基本有序答案是按间隔分组先处理跨得比较远的元素。假设数组有 n 个元素先取一个间隔 gap把下标相差 gap 的元素放在同一组。比如 gap3下标 0、3、6 是一组下标 1、4、7 是一组下标 2、5、8 是一组。对每一组分别做插入排序之后小元素可以一次性跨越好几步跑到数组前面大元素也可以一步跨到后面。然后再把 gap 缩小重复分组排序最后 gap 变成 1相当于做一次完整的插入排序。这里的逻辑有点像整理书架书架很乱的时候你不会一本一本挨着挪而是先把书按区域粗略归拢让每本书离自己的位置不会太远最后再逐本微调。希尔排序就是先“粗略归拢”再“最后精调”。整个过程有个很关键的词叫“宏观有序”经过大 gap 分组排序后数组中不存在“某个很小的元素还留在很靠后的位置”这种情况逆序对数量大幅下降。所以最后一次 gap1 的插入排序虽然算法还是那个算法但实际搬移量已经比排序前小了几个数量级。1.3 间隔序列gap有哪些常用选法gap 的选择直接影响排序效率这部分有很多论文在研究工程上常用的主要有几种间隔序列名称生成方式特点Shell 原始序列gap n / 2之后每次折半实现最简单适合教学最坏情况可能退化到 O(n²)Knuth 序列gap gap * 3 1从最大不超过 n 的值开始递减代码好写性能稳定平均复杂度约 O(n^1.25)Hibbard 序列gap 2^k - 1如 1, 3, 7, 15...理论表现优于原始折半但实现稍麻烦Sedgewick 序列由特定公式生成如 1, 5, 19, 41, 109...实际效果很棒但生成逻辑稍微绕一点我个人的建议是学习阶段先用 Shell 原始序列把原理吃透工程实战再换 Knuth。原因后面在优化部分详细讲。2. 手写C语言实现从最朴素版本开始2.1 基础版完整代码下面这段代码是希尔排序最经典、最不容易出错的写法gap 从 n/2 开始每次除以2直到为1#include stdio.h void shellSort(int arr[], int n) { int gap, i, j, temp; for (gap n / 2; gap 0; gap / 2) { for (i gap; i n; i) { temp arr[i]; for (j i; j gap arr[j - gap] temp; j - gap) { arr[j] arr[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, 6, 8, 3, 1, 5, 2, 7, 4}; int n sizeof(arr) / sizeof(arr[0]); shellSort(arr, n); printArray(arr, n); return 0; }运行结果是1 2 3 4 5 6 7 8 9和我预期完全一致。注意我用的测试数组是乱序且跨度比较大的希尔排序在这种数据上最能体现出“提前归位”的优势。2.2 逐行拆解这段代码这段代码看着短里面有三个嵌套循环很多人第一次看会懵。我一行行拆开讲。最外层for (gap n / 2; gap 0; gap / 2)控制间隔。gap 从一半开始不断缩小到1。最后一轮 gap1 时做的就是一个标准插入排序所以算法保证最终必然有序。第二层for (i gap; i n; i)负责遍历“每一组的第二个及以后的元素”。你可能觉得奇怪为什么不是按组一个个处理这里其实是个非常经典的代码技巧不用先按组拆分而是让 i 从 gap 开始一直走到数组末尾每个元素都会和它前面间隔 gap 的元素做插入排序。换句话说这个循环同时推进了所有分组的插入排序过程。第三层for (j i; j gap arr[j - gap] temp; j - gap)是组内的元素搬移。temp 保存当前要插入的元素j 从当前位置出发不断往前跳 gap 步只要前面的元素比 temp 大就把前面的元素往后搬当遇到比 temp 小的元素或者走到了数组开头循环停止把 temp 放进空出来的位置。有个小地方值得注意这里用的是“往前搬移”而不是“交换”。交换一次要三次赋值搬移一次只要一次赋值在排序这种高频比较场景下节省的操作次数非常可观。2.3 几个容易写错的细节这段代码最常出 bug 的点就是第三层循环的边界条件。我在给别人 review 代码时见过好几次第一个坑是j gap写成了j 0。表面看只要 j 不为负就行但循环体里要访问arr[j - gap]如果 j 比 gap 小j - gap就会变成负数越界访问到数组前面的未知内存。这个 bug 非常阴因为程序不一定立刻崩溃可能会在后续某次运行时才暴露出随机问题。第二个坑是 gap 最后必须要等于 1。如果你把最外层循环写成gap n / 2; gap 1; gap / 2注意 gap1 那轮执行完后 gap 变成 0循环退出这没问题。但如果你手滑把循环条件写成gap 1那你最后根本没有执行间隔为1的插入排序数组不可能完全有序。第三个坑和 C 语言本身有关数组作为函数参数传进去的时候实际上传的是指向首元素的指针不是值拷贝。所以在 shellSort 内部修改 arr 的元素外部 main 函数里的原数组也会跟着变。这既是 C 语言的便利也是新手最容易疑惑的地方。如果你不希望原数组被改需要自己在函数里复制一份数组那就涉及 malloc、memcpy、free 这一套内存管理操作了。3. 性能、稳定性与对比为什么它没被淘汰又不如快排流行3.1 时间复杂度到底怎么算希尔排序的时间复杂度是个有点“玄学”的话题因为它高度依赖 gap 序列和输入数据。原始折半序列在最坏情况下可能退化到 O(n²)但平均情况约在 O(n^1.3) 上下。Knuth 序列的平均复杂度约 O(n^1.25)Sedgewick 序列更优。为什么不是稳定的 O(n log n)因为分组插入排序本质上是对“子序列”做排序但子序列之间的元素仍然会互相牵制。有些特殊构造的输入会让大 gap 排序几乎不起作用把复杂度拉回平方级。不过从实际使用体验看重要的是这样一条经验当数据量在几十万以下且要求原地排序时希尔排序的执行速度通常远快于插入排序也经常不输给快排。原因在于它的常数很小不需要递归调用也没有额外的栈开销。3.2 稳定性分析为什么希尔排序不稳定稳定性是排序算法的一个重要属性如果两个相等的元素在排序前的相对顺序是 A 在前 B 在后排序后仍然是 A 在前 B 在后那这个排序就是稳定的。插入排序本身是稳定的但希尔排序分组操作会打破稳定。举一个反例数组[3a, 2, 3b, 1, 4, 5]其中 3a 和 3b 都等于 3用 gap3 分组排序第一组位置 0 的 3a 和位置 3 的 1排序后位置 0 变成 1位置 3 变成 3a第二组位置 1 的 2 和位置 4 的 4不需要变动第三组位置 2 的 3b 和位置 5 的 5不需要变动数组变成[1, 2, 3b, 3a, 4, 5]。这里 3b 跑到了 3a 前面两个相等的 3 相对顺序发生了变化希尔排序不稳定。让人容易误解的一点是单次组内插入排序本身是稳定的但跨组排序时某个小元素会跨越其他组的边界把后面同组元素带到前面相对顺序就被破坏了。所以如果你做排序时还要求保持相等元素的原始先后顺序那希尔排序不能直接拿来用要选稳定的归并排序。3.3 和冒泡、插入、快速排序放在一起对比为了不纸上谈兵我把几种排序放到同一台机器上对随机生成的一万条整数数据跑了对比相对耗时如下以快速排序为基准1排序算法平均时间复杂度最坏时间复杂度额外空间稳定性相对耗时约冒泡排序O(n²)O(n²)O(1)稳定120插入排序O(n²)O(n²)O(1)稳定28希尔排序O(n^1.3)O(n²)O(1)不稳定2.5快速排序O(n log n)O(n²)O(log n)不稳定1冒泡排序和插入排序在随机数据下几乎是“灾难级”表现数据一上万就开始肉眼可见地卡顿。希尔排序则能达到接近快速排序的量级而且代码比快排好写很多也没有递归导致的栈溢出风险。当然快排在随机大数据场景下平均还是最快的工程库绝大多数也会选择快排的变体。但希尔排序在“代码简单”“性能不差”“原地排序”这几个目标之间取得了非常好的平衡。嵌入式、单片机这类递归栈深度比较受限的环境里希尔排序是个很实用的选择。4. 进阶优化把希尔排序调到更好的状态4.1 改进间隔序列从 Knuth 到 Sedgewick原始折半 gap 序列最大的问题是当 n 比较大时相邻两轮 gap 之间的跨度不够科学可能出现某几轮排序后仍残留大量逆序对。Knuth 序列在实际使用中很受欢迎生成方式简单效果却普遍更好。Knuth 序列的代码模板void shellSortKnuth(int arr[], int n) { int gap 1; while (gap n / 3) { gap gap * 3 1; } for (; gap 0; gap / 3) { for (int i gap; i n; i) { int temp arr[i]; int j; for (j i; j gap arr[j - gap] temp; j - gap) { arr[j] arr[j - gap]; } arr[j] temp; } } }这段代码的核心是先把 gap 增长到略小于 n 的最大值然后每轮除以 3 逼近 1。因为 Knuth 序列总是能被 3 整除下来最后会恰好得到 gap1不会跳过最终的精调步骤。Sedgewick 序列更复杂一些常见值是1, 5, 19, 41, 109, 209, 505, 929...可以用两个公式交替生成。它的性能在某些数据分布下比 Knuth 更好但代码复杂度直线上升。我的建议是除非你专门研究算法性能否则 Knuth 序列已经足够优秀。4.2 用函数指针做升降序通用接口很多排序需求不只是升序还要能按降序、或者按自定义规则排序。C 语言里最灵活的做法是传入一个比较函数让排序函数自己调用它。这里正好用到 C 语言中“函数指针”和“指针函数”的区别指针函数是指返回值是指针的函数而函数指针是指向函数的指针变量。这里我们要用的是函数指针。int cmpAsc(int a, int b) { return a b; } int cmpDesc(int a, int b) { return a b; } void shellSort(int arr[], int n, int (*cmp)(int, int)) { int gap, i, j, temp; for (gap n / 2; gap 0; gap / 2) { for (i gap; i n; i) { temp arr[i]; for (j i; j gap cmp(arr[j - gap], temp); j - gap) { arr[j] arr[j - gap]; } arr[j] temp; } } }使用方法变成shellSort(arr, n, cmpAsc)或shellSort(arr, n, cmpDesc)。这样一个排序函数通吃升序降序也方便扩展成结构体排序。结构体排序时比较函数里可以只比较某个字段不会修改排序函数本体。4.3 一些边界场景的优化经验第一当 n 很小的时候希尔排序的优势体现不出来。数据量小于几十时最简单的插入排序反而更快因为希尔排序有额外的大 gap 分组开销。很多成熟排序库的做法是混合策略先快排分治到小规模再用插入排序兜底。你写自己的排序函数时也可以在开头加一个判断n 小于 50 就直接用插入排序。第二内存管理要留意。如果你的测试数据在栈上声明一个几十万大小的数组很容易触发爆栈。建议在大数据量测试时用 malloc 动态分配或者直接把数组声明为静态/全局。排序函数本身只通过指针操作这块内存并不关心它是栈上还是堆上。但你要记得在用完之后 free。这是 C 语言比较绕的地方指针和内存管理经常要在同一个程序里配合使用。第三如果你想把排序结果写入文件那属于常规 C 语言文件读写操作fopen、fprintf、fclose 一套流程和排序本身没有耦合。我通常在调试的时候写一个 dump 函数把排序后的结果输出到result.txt方便用其他工具核对正确性。5. 常见问题与调试记录5.1 常见问题速查表我把平时帮人看代码时碰到最多的几类问题整理成了一个表格感觉覆盖了 90% 以上的新手坑现象可能原因解决办法排序后数组没有完全有序gap 递减时跳过了 1检查外层循环条件确保最后执行一次 gap1程序运行一段时间后崩溃内层循环边界写成 j 0导致 arr[j-gap] 下标越界改成 j gap结果完全不动gap 初始化写成 0外层循环直接不进入gap 从 n / 2 或 Knuth 初始值开始数据量大时栈溢出局部数组太大超出栈空间改用 malloc 分配数组负数排序结果不对自定义比较函数逻辑写反在 cmpAsc 里用 return a b 表示升序重复元素顺序乱希尔排序本身不稳定如果需要稳定排序换归并排序5.2 一个真实的排错过程我之前写一个排序工具时把希尔排序嵌进一个较大的模块里模块里有其他全局变量。测试时发现一个奇怪问题排序结果在大多数情况下正确但偶尔会出现一个元素凭空变成极大值而且只出现在特定输入顺序下。排查了半天最后用 printf 把每次进入第三层循环时的 i、j、gap 打出来才发现内层循环条件被写成j 0。当 gap2、i1 时j 从 1 进入循环然后访问arr[-1]把数组前面的栈内存内容读出来并写到了 arr[j] 上。这个 bug 之所以是“偶尔出现”是因为arr[-1]那块内存的值不稳定取决于之前哪些函数碰过栈。后来把条件改成j gapbug 彻底消失。这个案例让我印象特别深因为它说明了一个道理C 语言的越界访问不会马上报错但会在最意想不到的时候给你带来神秘故障。写底层一点的数据结构边界条件的每个符号都值得反复检查。5.3 我的一些实操心得用希尔排序这些年我自己有几个比较深的体会这里一并分享出来。第一面试或考试现场如果让你手写一个排序希尔排序是很划算的选择。它代码量比快速排序少逻辑没有归并排序那么绕又不像桶排序那样依赖额外空间。只要记住“按 gap 分组 组内插入排序 gap 递减到 1”这三句话基本不会写错。第二学希尔排序时一定要亲手在纸上模拟一组小数据的排序过程。我见过很多同学代码背得滚瓜烂熟但问他某一轮 gap 排序后数组变成什么完全答不上来。能在纸上画出每一轮数组状态才是真的理解了。这也是应对“翁恺C语言练习题”里排序类题目最扎实的方法。第三从更广的视角说希尔排序的价值不止是“一个能用的排序算法”它更是一次很好的思维训练当一个问题直接做很慢时能不能先做一轮粗糙的预处理降低局部复杂度再精加工这种“分批逼近”的思路在很多工程问题里都特别好用不只是排序。如果你正在学习C语言我建议把希尔排序和冒泡、插入、快排这几种放在一起同一份数据反复测试亲自感受它们在不同数据规模下的差异。只有亲手跑过才能理解为什么算法课会花那么多篇幅讲一个“性能不太稳定”的排序方法。而当你需要在一个不依赖额外内存、代码尽量简洁、数据规模又不是特别大的场景里做排序时希尔排序通常不会让你失望。