直接插入排序、折半插入排序、希尔排序这三个名字只要学过数据结构的人都不会陌生。但说实话我在带新手做练习的时候发现很多人是“代码背下来了细节完全没懂”为什么折半插入排序的插入位置是low为什么希尔排序明明看起来挺规整却会被标记为“不稳定”这些问题一旦被追问立刻就卡壳。这篇内容会把三种插入排序从头到尾拆开来讲从排序过程模拟、C语言代码实现到时间空间复杂度分析、稳定性判断再到我这些年调试中踩过的边界条件坑一次性说清楚。适合正在学数据结构的学生、准备笔试面试的开发者也适合想系统梳理排序细节的同行。1. 写在前面的“总画像”这三种排序其实是一家人1.1 为什么要把三种算法放一起学很多人学排序是“一个一个记”直接插入一个、折半插入一个、希尔排序一个然后到面试时发现记混了。问题不在于记性不好而在于你没看到它们的血缘关系。直接插入排序是所有插入类排序的底座它的逻辑一句话就能说清把新元素往前面已经有序的序列里插插完还是有序。折半插入排序没有改变这个底座它只是把“从后往前一个个找插入位置”升级成了“用二分查找定位”省的是比较次数。希尔排序则走得更远它先把序列按照间隔分组在组内做直接插入然后不断缩小间隔最后间隔变成1时再整体做一次直接插入。换句话说折半插入是“在同一个算法内部优化查找”希尔是“在另一个维度上做预排序”。把三者放在一起你会看到一条清晰的优化主线先追求正确再降低单个操作成本再想办法减少元素移动的总次数。1.2 一个共同主题增量缩小与控制比较插入排序家族有一个共通的无形线索每一趟处理完之后序列的“有序程度”都在提升。直接插入每趟把一个元素放到正确位置折半插入只是放得更快希尔则是通过区间跳跃让较小的元素快速向前移动减少后续整体的移动工作量。如果把“逆序对”拿出来讲这条线索会更清楚。逆序对就是一对元素位置靠前的值反而大于位置靠后的值。直接插入排序每交换一对相邻元素只能消除一个逆序对最坏情况下要交换几乎每一对于是复杂度到了 O(n²)。希尔排序的跨越式移动一次交换可以跨过好几个位置一次就消除好几个逆序对所以它能在同样 O(n²) 级别的“最坏保障”下把平均表现拉到一个明显更好的水平。这就是理解希尔排序“为什么能快”的关键不是它做了什么神奇的事而是它绕过了相邻交换的低效。2. 直接插入排序最朴素的“扑克牌理牌法”2.1 思路还原与一趟排序过程直接插入排序的思路和你打扑克时理牌一模一样。你左手已经拿了一撮按大小排好的牌新摸到一张牌时会从右往左一张张比找到合适的位置插进去。用数组来讲第一趟时我们把数组的第一个元素当成“已经有序的左手牌”从第二个元素开始每一个都当成新摸到的牌。以数组 [49, 38, 65, 97, 76, 13, 27] 为例初始[49, 38, 65, 97, 76, 13, 27]假设下标0的49已在手。处理38先暂存38往前看49比38大把49往后移一位38放到最前面。结果[38, 49, 65, 97, 76, 13, 27]。处理6565比前面的49大不需要移动。结果不变。处理97也比前面大不动。处理76往前看97比76大往后移65比76小停76插入到97原来的位置。结果[38, 49, 65, 76, 97, 13, 27]。处理13它比前面所有元素都小一路比较一路往后移最后放到最前面。结果[13, 38, 49, 65, 76, 97, 27]。处理27类似最后插到13和38之间。结果[13, 27, 38, 49, 65, 76, 97]。每一趟结束后前 i1 个元素都是有序的。注意这里说的“有序”是局部有序后面的元素还没参与进来但前面已经是完整排序完成后的样子这一点和选择排序截然不同。2.2 代码实现的两种写法普通版与哨兵版最直白的写法如下void insertion_sort(int a[], int n) { int i, j, key; for (i 1; i n; i) { key a[i]; j i - 1; while (j 0 a[j] key) { a[j 1] a[j]; j--; } a[j 1] key; } }核心逻辑就三条暂存当前值往前找位置把比它大的元素依次往后挪。循环结束后 j 停在第一个不大于 key 的位置所以a[j1] key就是插入点。很多教材还会讲一种“带哨兵”的写法。它的前提是数组下标从1开始a[0]空出来专门当哨兵void insertion_sort_sentinel(int a[], int n) { int i, j; for (i 2; i n; i) { a[0] a[i]; j i - 1; while (a[j] a[0]) { a[j 1] a[j]; j--; } a[j 1] a[0]; } }哨兵版本把待插入的值提前放到a[0]这样while循环里不需要再写j 0这个判断。因为就算 j 一直退到0a[0]等于待插入值a[j] a[0]会变成a[0] a[0]永远为假循环自然会停。少一个条件判断在数据量大时能省下不少比较指令这就是哨兵的意义。不过哨兵写法有三个隐藏前提数组容量必须至少 n1a[0]只能作为临时存储排序结果不包含它如果待插入元素是结构体等复杂对象复制到哨兵位有额外开销这种场景下普通写法反而更安全。2.3 复杂度与稳定性判断直接插入排序的时间复杂度分层看非常清晰最好情况是数组已经有序每趟只需要比较一次、移动零次总比较次数是 n-1时间复杂度 O(n)最坏情况是数组完全逆序第 i 趟要比较 i 次、移动 i 次总次数是 12...(n-1)即 O(n²)平均情况也是 O(n²)。空间复杂度 O(1)属于原地排序。稳定性方面关键在于代码里用的是a[j] key而不是a[j] key。只有严格大于当前值时才会移动元素遇到相等值就停下来了所以后出现的相等元素会被插到先出现元素的后面相对顺序不变因此直接插入排序是稳定排序。这里我提醒一个容易混淆的点稳定性的判断依据不是“算法看起来像不像稳定”而是代码里的严格不等号。如果你把改成相等时也会继续往前移动那这个“看似相同”的算法就变成不稳定的了。很多笔试题会在这里设陷阱。3. 折半插入排序把“找位置”优化成二分查找3.1 优化点在哪里直接插入排序的插入过程是“边比较边移动”它把“找位置”和“腾位置”混在一起做。但是仔细分析你会发现其实两个环节的成本要分开看比较的次数决定了你判断位置的代价移动的次数决定了你搬动元素的代价。直接插入排序在逆序情况下每趟插入一个新元素最多要跟前面所有已经有序的元素比较一遍。这会浪费大量比较操作因为前面已经是有序序列了完全可以用二分查找快速定位插入位置。这就是折半插入排序的思路先用二分查找找到该插入的位置再一次性把该位置之后的所有元素整体后移最后放入待插入值。代码实现也直观void binary_insertion_sort(int a[], int n) { int i, low, high, mid, key; for (i 1; i n; i) { key a[i]; low 0; high i - 1; while (low high) { mid (low high) / 2; if (a[mid] key) high mid - 1; else low mid 1; } for (int j i - 1; j low; j--) a[j 1] a[j]; a[low] key; } }这里二分查找结束后low指向的位置就是插入点。为什么不是high因为循环结束条件是low high此时low high 1low正好是第一个大于 key 的元素位置把待插入元素放到这里就能保证它前面所有元素都小于等于 key。3.2 稳定写法的一个细节折半插入排序有个非常反直觉的稳定性细节二分查找时遇到a[mid] key的情况必须往右半区走也就是执行low mid 1而不是往左走。原因在于只有当a[mid] key时我们才向左收缩搜索区间。等于时不收缩到左半区最后得到的low会是“第一个大于 key”的位置也就是说把所有等于 key 的元素都留在前面新元素插在它们后面相等元素的相对顺序得以保持。如果反过来把判断写成a[mid] key才向左收缩那么相等的元素会被定位到插入点之前后出现的相等元素反而跑到前面去了稳定性就被破坏。我见过不少教材和网上的代码在这里写得比较含糊面试时如果被问到“折半插入排序是不是稳定的”你就回答“稳定但前提是二分的等于分支必须向右收缩”这一句就能显出功底。3.3 折半插入真的变快了吗这个优化确实减少了比较次数。直接插入排序最坏情况下需要约 n²/2 次比较折半插入排序每趟折半查找只需约 log₂i 次总比较次数降到 O(n log₂n) 量级这在数据量较大时是一个可感知的改进。但问题在于移动次数一分没少。插入一个元素时为了腾出位置插入点后面的所有元素仍然要依次后移最坏情况下每趟移动 i 次总移动次数还是 n²/2 量级。由于移动元素比比较元素更耗时折半插入排序的时间复杂度从数量级上看依然是 O(n²)只是在常数上比直接插入排序更优。这也是为什么它常被当成“优化思想的练习”却很少在实战中被单独拿出来用。另外注意一点折半插入排序依赖于数组的随机访问能力它只能在顺序表上发挥优势。如果底层是链表二分查找就没法实现了做插入还得从头遍历优化效果归零。4. 希尔排序跨大步减少逆序对4.1 核心机制与分组排序演示希尔排序的关键动作是“分组 减步长”。先选一个间隔 gap把下标相差 gap 的元素分到同一组组内做直接插入然后缩小 gap 再重复最后 gap 等于1时整个数组做一次完整的直接插入排序。用数组 [49, 38, 65, 97, 76, 13, 27, 49] 来模拟初始 gap 4分组下标0和4一组(49, 76)下标1和5一组(38, 13)下标2和6一组(65, 27)下标3和7一组(97, 49)。组内直接插入后第一组不变第二组变(13, 38)第三组变(27, 65)第四组变(49, 97)。数组变为[49, 13, 27, 49, 76, 38, 65, 97]。然后 gap 2分组下标0, 2, 4, 6 一组(49, 27, 76, 65)排序后(27, 49, 65, 76)下标1, 3, 5, 7 一组(13, 49, 38, 97)排序后(13, 38, 49, 97)。数组变为[27, 13, 49, 38, 65, 49, 76, 97]。最后 gap 1做一次普通直接插入排序得到 [13, 27, 38, 49, 49, 65, 76, 97]。可以看到前两趟虽然没有让序列全局有序但已经把较小的元素大幅往前挪了。最后一趟直接插入排序面对的几乎是一个“基本有序”的序列移动次数很少整体效率因此得到提升。核心代码如下void shell_sort(int a[], int n) { int gap, i, j, key; for (gap n / 2; gap 0; gap / 2) { for (i gap; i n; i) { key a[i]; j i - gap; while (j 0 a[j] key) { a[j gap] a[j]; j - gap; } a[j gap] key; } } }内层循环是把标准直接插入排序中的步长从1换成了gap每一组轮流处理。注意 gap 1 时它就会自动退化成标准直接插入排序所以希尔排序的正确性由最后一趟保证。4.2 gap怎么选不同序列对效率的影响希尔排序最微妙的地方是 gap 的选择。上面代码用的折半递减方案最简单但绝不是最优的。如果 gap 的倍数关系设置不当比如某些元素始终不进同一组它们之间的逆序对就要拖到 gap1 那趟才处理性能会明显下降。实践中常见的改进包括 H 序列3h 1和 Sedgewick 序列。H 序列从1开始每次按3 * h 1增长反过来作为 gap 使用也就是先算出一个接近 n/3 的数然后依次缩小。这种选法可以让不同组之间的元素更快地跨组交换平均表现比普通折半方案好很多。希尔排序的时间复杂度与 gap 序列强相关。最坏情况下使用某些劣质序列会退化到 O(n²)而使用较好的序列可以把最坏情况压到 O(n^1.5) 甚至更低平均情况在 O(n^1.3) 左右。因此有关希尔排序复杂度的面试题最准确的回答是“取决于 gap 序列”而不是像直接插入那样直接给出一个确定值。4.3 为什么希尔排序不稳定附反例希尔排序不稳定的根本原因是元素被分到不同组组内排序时可能跨越多个位置交换而相等的元素可能恰好分属不同组排序后它们的相对顺序就可能颠倒。构造一个轻量反例数组 [1, 3a, 5, 2, 3b]其中 3a 和 3b 数值相等我们约定 3a 表示原数组中靠前的那个3。取 n 5gap 2 时分成两组下标0, 2, 4 一组(1, 5, 3b)组内排序后变为(1, 3b, 5)。下标1, 3 一组(3a, 2)组内排序后变为(2, 3a)。合并数组后得到[1, 2, 3b, 3a, 5]。原本应该是 3a 在 3b 前面现在 3b 跑到 3a 前面了相对顺序被破坏。这个反例虽然简单但在理解希尔排序的非稳定性时非常有用。它也在提示你一个工程经验如果业务要求稳定排序不要碰希尔排序直接选择归并排序或者直接插入排序。5. 三种排序的横向对比与实战选型5.1 复杂度与特性速查表把三种排序放在一张表里优缺点会非常直观排序方式最好时间复杂度平均时间复杂度最坏时间复杂度空间复杂度稳定性关键劣势直接插入排序O(n)O(n²)O(n²)O(1)稳定数据量大且乱序时慢折半插入排序O(n log n)O(n²)O(n²)O(1)稳定移动次数没有减少希尔排序与gap相关约O(n^1.3)与gap相关可能O(n²)O(1)不稳定gap选取不当会退化补充一个细节折半插入排序的“最好情况”在教材里有些争议因为它即使面对有序数组每趟也要做约 log₂i 次二分查找不能像直接插入那样只比较一次就结束所以总时间为 O(n log n)。在平均和最坏情况下由于移动操作占主导整体仍然是 O(n²)。5.2 真实工程中的应用场景三种排序在实际项目中依然有存在感。直接插入排序适用于两类工况一是数据量很小比如十几个元素此时它比快排更快因为快排有递归和分区的固定开销二是数据基本有序比如日志数据按时间追加后再插入少量新数据直接插入排序一趟下来几乎是 O(n) 的。折半插入排序的实战价值偏弱但它是理解“比较与移动分离优化”的最佳范例。在笔试基础题里它常被用来测试对二分查找边界条件的掌握程度。如果你在工作中遇到有人把它用在顺序表的中大批量排序上说明数据规模还没大到需要上归并或快排或者干脆是教学场景。希尔排序的工程定位是“不要求稳定、数据规模中等、希望比 O(n²) 快一截”的场景。它实现起来比快排简单没有递归不需要额外空间对嵌入式等内存受限环境比较友好。很多老的嵌入式代码里还能见到希尔排序的身影就是因为它的代码紧凑、空间只有 O(1)。6. 排序代码调试与踩坑笔记6.1 三个最容易翻车的边界条件排序类代码的坑通常不在算法思想而在循环边界。第一个坑是while (j 0 a[j] key)里的j 0忘写。少了它j 退到 -1 时访问a[-1]会造成数组越界轻则结果错乱重则直接段错误。使用哨兵写法时这个判断可以省略但如果数组下标从0开始却错用了哨兵写法a[0]被当成哨兵后第一个元素就会丢失。第二个坑是折半插入排序结束时插入位置的确定。很多人搞不清该用low还是high保险的做法是记住循环结束后一定满足low high 1插入位置就是low。写a[high1] key也等价但写a[low] key更直观也不容易把边界弄混。第三个坑是希尔排序中内层循环的起点和步长。for (i gap; i n; i)不能改成for (i 0; i n; i gap)后者只会处理每一组的第一个元素丢失后续的组内插入逻辑。正确写法是让 i 从 gap 开始逐个递增每一轮把 a[i] 往前插入到它自己所在的那个组里。这块建议多打断点看两趟运转理解“外层遍历所有元素、内层通过减 gap 回跳”的结构。6.2 我常用的调试三板斧写排序算法时我一般会做三件事。第一用随机数组 小规模数据验证数组长度固定不超过10自己手工推一遍结果再用下面这段辅助逻辑校验整个序列是否非降序void check_sorted(int a[], int n) { for (int i 1; i n; i) { if (a[i - 1] a[i]) { printf(排序失败: a[%d]%d, a[%d]%d\n, i-1, a[i-1], i, a[i]); return; } } printf(排序正确\n); }第二打印每一趟的数组状态。特别对希尔排序把 gap 和每趟结果打出来和手推结果逐行对比通常一眼就能发现是哪一组排序出了问题。第三用极端数据测试边界空数组、只有一个元素、完全逆序、全部相等。全部相等这个用例容易被忽略它能测出稳定性相关代码是否正确。全部相等时直接插入排序和折半插入排序都应当任何元素都不移动位置如果发现走动说明比较条件写错了。6.3 一个容易被忽略的面试追问点最后一个容易被追问的点是直接插入排序对链表排序时不需要移动元素但需要从头查找插入位置所以时间仍为 O(n²)空间 O(1)而且是稳定的。而折半插入排序在链表上无法实现二分优势完全消失。希尔排序在链表上更是难以高效实现因为随机访问跨组元素成本很高。这类追问考察的不只是算法本身而是“算法与数据结构是否匹配”的意识。我在实际面试别人时经常会让候选人现场推导一遍希尔排序的稳定性反例。能写出上面那个 [1, 3a, 5, 2, 3b] 例子的人基本上说明他对排序过程有真正的理解而不是只记住了“希尔排序不稳定”这个结论。最后分享一点个人习惯关于排序我这些年最大的体会是不要靠死记硬背代码学算法一定动手模拟过程。每学一种排序我就找一组包含相同元素的小数组拿纸笔走一遍排序流程同时在草稿纸上记录每一趟的数组状态。这个过程看着笨但能把“为什么代码要这么写”彻底想明白。尤其建议你自己动手把三种排序从一个“模板”改造出来先写一个标准的直接插入排序然后改成折半插入再改成带 gap 的希尔排序。三次改动之后你会很自然地理解它们之间的演进关系。以后不管面试考什么边界变体都能从根上推导而不是靠背诵碰运气。