直接插入排序和希尔排序这两个东西放在排序算法家族里属于“看着简单、写起来容易翻车”的典型代表。很多人学排序的时候冒泡和选择排序过一遍就觉得自己懂了一到插入排序觉得“不就是往前面挪一挪嘛”结果真上手写代码边界条件一塌糊涂再往深了走到希尔排序增量序列怎么选、为什么它能比直接插入快、分组插入的循环到底怎么写一堆问号就冒出来了。我当年第一次手写希尔排序的时候外层循环的步长更新写错了位置跑出来的结果看着像排好了实际上部分元素根本没参与比较调了半天才定位到问题。这篇内容就是把我对这两个算法的理解、实操中踩过的坑、以及面试和工程里真正用得上的细节完整地摊开讲一遍。不管你是刚接触数据结构的学生还是工作几年想把基础重新夯实一遍的开发者都能从里面找到可以直接抄作业的代码模板和避坑清单。1. 先搞清楚这两个算法到底在解决什么问题1.1 从“整理扑克牌”说起插入排序的直觉来源直接插入排序的核心思想用生活场景解释最清楚你手里有一把扑克牌左手是已经理好的牌右手是还没理的牌。每次从右手抽一张插入到左手合适的位置左手始终保持有序。这个动作你打牌的时候做了无数遍根本不用想但翻译成代码就需要把“找位置”和“腾空间”这两件事拆开。具体到数组上我们把数组分成两部分前面一部分是已排序区间后面一部分是未排序区间。初始时已排序区间只有一个元素第一个元素天然有序然后每次取未排序区间的第一个元素在已排序区间里从后往前扫描找到合适位置插入进去同时把比它大的元素统统往后挪一位。这个过程重复到未排序区间为空整个数组就有序了。为什么是从后往前扫描而不是从前往后因为插入的同时需要腾位置。从后往前扫遇到比当前元素大的就往后挪一格挪到遇到比它小的或者到头了空出来的那个位置就是插入点。一趟扫描同时完成了“找位置”和“腾空间”不需要额外开数组空间复杂度是 O(1)。如果从前往后找位置找到之后还得把后面所有元素整体后移虽然结果一样但代码写起来别扭而且容易把下标搞乱。这里有个很多人忽略的细节插入排序是稳定排序。所谓稳定就是值相等的元素在排序后相对顺序不变。从后往前扫描时我们只在“严格大于”的时候才往后挪遇到相等就停下来插入这样相等元素的相对次序就保住了。这个性质在需要多关键字排序的场景里非常有用比如先按成绩排、再按姓名排稳定性保证了第二次排序不会打乱第一次的结果。1.2 希尔排序不是“另一种插入排序”而是插入排序的加速器很多人第一次看到希尔排序会觉得这是不是个完全不同的新算法。其实它的本质还是插入排序只不过做了一件很聪明的事先让数组变得“基本有序”再用直接插入排序收尾。直接插入排序有个致命弱点如果数组是逆序的比如[5,4,3,2,1]每次插入都要把前面所有元素挪一遍时间复杂度退化到 O(n²)。但如果数组本来就接近有序插入排序的效率极高接近 O(n)。希尔排序就是利用了这个特性——它先按一个较大的间隔增量把数组分成若干组对每组做插入排序。这时候元素可以“大步跳跃”地往正确位置靠拢而不是一步一步挪。随着增量逐渐缩小数组越来越有序最后增量变成 1做一次标准的直接插入排序此时数组已经基本有序这一趟几乎不需要挪动多少元素。打个比方直接插入排序像是每次只能挪一格搬家希尔排序像是先允许你跨楼层搬最后再在一层内微调。跨楼层搬的时候虽然看起来乱但大件家具很快就到了大致楼层最后微调的工作量就小得多。增量的选择是希尔排序的灵魂。最经典的是希尔增量n/2, n/4, n/8 ... 直到 1。这个序列简单好记但最坏情况下时间复杂度仍然是 O(n²)。后来有人提出了 Hibbard 增量1, 3, 7, 15...即 2^k - 1、Sedgewick 增量等更优的序列能把最坏复杂度降到 O(n^1.5) 甚至更好。实际工程中希尔增量因为实现简单、常数小在中等规模数据上表现并不差所以很多教材和面试题默认用它。1.3 两者的复杂度与适用场景对照把关键指标摆在一起看选择就清晰了对比维度直接插入排序希尔排序平均时间复杂度O(n²)取决于增量序列希尔增量为 O(n^1.5) 左右最坏时间复杂度O(n²)希尔增量下 O(n²)优化增量可改善最好时间复杂度O(n)已有序O(n log n) 量级空间复杂度O(1)O(1)稳定性稳定不稳定适用数据规模小规模n 100 左右中等规模几千到几万实现难度极低低但循环边界易错直接插入排序适合数据量小、或者数据已经基本有序的场景。很多标准库在数组长度小于某个阈值比如 16 或 32时会退化成插入排序因为小数组上它的常数因子比快排还小。希尔排序则适合中等规模、对稳定性没有要求、又不想引入递归或额外空间的场景比如嵌入式环境里对一段采集数据做排序。注意希尔排序是不稳定排序。分组插入的时候相等的元素可能被分到不同组相对顺序无法保证。如果业务要求稳定性老老实实用插入排序或者归并排序。2. 直接插入排序的代码骨架与边界陷阱2.1 一份可以直接背下来的标准实现先上代码用 Python 写因为它的列表操作直观换成 C/Java 逻辑完全一样def insertion_sort(arr): n len(arr) for i in range(1, n): key arr[i] j i - 1 while j 0 and arr[j] key: arr[j 1] arr[j] j - 1 arr[j 1] key return arr这段代码短到可以背下来但每一行都有讲究。i从 1 开始因为下标 0 的元素天然属于已排序区间。key保存当前要插入的元素这一步至关重要——如果不保存后面挪动元素的时候会把arr[i]覆盖掉数据就丢了。j从i-1开始往前扫while条件里j 0必须放在前面因为 Python 的and是短路求值如果先写arr[j] key当j变成 -1 时会访问arr[-1]在 Python 里这是最后一个元素逻辑直接错乱在 C/Java 里则直接数组越界崩溃。循环结束后j1就是插入位置。为什么是j1而不是j因为循环退出时要么j变成了 -1说明 key 比所有已排序元素都小应该插到最前面即下标 0正好是j1要么arr[j] key说明 key 应该插在j的后面也是j1。这个j1的统一性很多人第一次写会绕进去建议拿[3,1,2]手动走一遍。2.2 为什么 while 循环里必须先判断 j 的边界上面提到的短路求值问题值得单独拎出来说。我见过不少人在 C 语言里写成while (arr[j] key j 0) { ... }这在j变成 -1 的瞬间就会读取arr[-1]属于未定义行为可能读到垃圾值可能直接段错误。正确写法必须把边界判断放前面while (j 0 arr[j] key) { ... }这个顺序问题在 Python 里更隐蔽因为 Python 的负索引不会报错arr[-1]会悄悄返回最后一个元素导致排序结果看起来“差不多对”但个别元素位置错误排查起来极其痛苦。我建议养成肌肉记忆凡是往前扫描的循环边界判断永远写在条件最左边。2.3 用哨兵优化减少一次比较多数场景没必要有些教材会提到“哨兵”技巧把数组第 0 位留空存放当前要插入的元素作为哨兵这样 while 循环里就不用判断j 0了因为哨兵一定会在边界处停下来。这个技巧在 C 语言里能省一次比较理论上略微提升性能。但实际工程中我不推荐这么做。原因有三第一它要求数组从下标 1 开始存数据破坏了 0-based 的通用约定调用方容易踩坑第二省下的那次比较在现代 CPU 的分支预测面前收益微乎其微第三代码可读性下降维护成本上升。除非你在写对性能极度敏感的底层库否则标准写法完全够用。这个技巧知道有这么回事就行面试时提一嘴能加分实际项目里别给自己找麻烦。2.4 插入排序在真实代码里的“隐藏出场”插入排序最容易被低估的地方是它在工业级排序库里的角色。很多语言的标准库排序实现是混合策略大规模数据用快排或归并但当子数组长度小于某个阈值时切换到插入排序。原因是插入排序虽然渐近复杂度差但它的常数因子极小——没有递归调用开销、没有额外内存分配、循环体里就是简单的比较和赋值在小数组上跑得比快排还快。以常见的实现为例阈值通常设在 16 到 32 之间。这个数字不是拍脑袋定的而是实测出来的平衡点数组再大一点O(n²) 的劣势开始显现再小一点快排的递归开销占比过高。你在自己写排序工具时也可以借鉴这个思路比如对一个可能包含大量小分片的列表做排序先判断长度小于 20 就直接插入排序省去递归的麻烦。3. 希尔排序的增量逻辑与循环嵌套拆解3.1 从“分组”到“增量缩小”的完整推演希尔排序的代码比插入排序多一层循环但很多人卡在“到底哪层循环控制什么”上。我们一步步推。最外层是增量gap的递减循环从n//2开始每次减半直到gap 1。这一层决定了“分组的大小”。当gap 4时下标 0 和 4 是一组1 和 5 是一组以此类推每组内部做插入排序。中间层是i从gap遍历到n-1。为什么从gap开始因为每组的前gap个元素下标 0 到 gap-1分别是各组的第一个元素天然有序不需要处理。从gap开始每个元素都属于某个组需要往它所在组的前面插入。最内层就是标准的插入排序逻辑只不过往前扫描的步长是gap而不是 1。j从i-gap开始每次减gap比较和挪动都按gap的间隔进行。def shell_sort(arr): n len(arr) gap n // 2 while gap 0: for i in range(gap, n): key arr[i] j i - gap while j 0 and arr[j] key: arr[j gap] arr[j] j - gap arr[j gap] key gap // 2 return arr注意arr[j gap] arr[j]和最后的arr[j gap] key这里的gap对应插入排序里的1。因为挪动的步长是gap空出来的位置自然也是jgap。这个对应关系想通了希尔排序的代码就是插入排序把所有的1换成gap。3.2 增量序列的选择希尔增量不是唯一答案前面代码用的是希尔增量n/2 递减它简单但有个已知的弱点当gap较大时分组里元素少排序快但当gap缩小到某些值时可能出现“前面几轮白干了”的情况——某些元素在大的 gap 下被挪来挪去到了小的 gap 又被打回原形。最坏情况下复杂度仍是 O(n²)。如果想追求更好的性能可以换增量序列。Hibbard 增量是1, 3, 7, 15, ...通项是2^k - 1最坏复杂度 O(n^1.5)。Sedgewick 增量是1, 5, 19, 41, 109...最坏复杂度约 O(n^1.33)。实现上只需要把gap n//2; gap // 2换成预定义的序列倒序取用即可def shell_sort_hibbard(arr): n len(arr) gaps [] k 1 while (1 k) - 1 n: gaps.append((1 k) - 1) k 1 for gap in reversed(gaps): for i in range(gap, n): key arr[i] j i - gap while j 0 and arr[j] key: arr[j gap] arr[j] j - gap arr[j gap] key return arr实际选哪个我的经验是数据量在几千以内希尔增量和 Hibbard 增量实测差距不明显用希尔增量代码更短数据量上万且对性能有要求可以上 Hibbard 或 Sedgewick。但要注意增量序列的最后一个值必须是 1否则最后无法保证完全有序——这是硬性约束忘了就是逻辑错误。3.3 一个真实踩过的坑gap 更新位置写错导致“假排序”我第一次写希尔排序时把gap // 2写在了for i循环的内部结果每处理一个元素 gap 就减半循环提前结束数组只排了个大概。更坑的是测试用例用的是[3,1,2]这种小数组跑出来居然是对的直到换成[5,3,8,1,9,2,7,4,6]才暴露问题——部分元素根本没被比较到。这个坑的教训是gap 的更新必须在外层 while 循环的末尾等所有分组都处理完一轮之后才缩小。判断方法很简单在gap // 2那行打个断点或者打印一下看每轮 gap 的值是不是4, 2, 1这样递减如果看到4, 2, 1, 0中间夹杂着奇怪的数字就是位置写错了。还有一个隐蔽的变体错误while gap 0写成while gap 0当 gap 变成 0 时range(0, n)会正常执行但内层j i - 0 iarr[j0] arr[j]自己赋值给自己然后j - 0永远不变直接死循环。这个错误在 Python 里表现为程序卡死在 C 里也是死循环排查时容易误以为是数据量太大。记住gap 的终止条件是严格大于 0。4. 手写测试用例怎么验证你的排序真的对了4.1 别只用“看起来有序”的数组做测试很多人测试排序算法随手写个[3,1,2]跑一下输出[1,2,3]就认为对了。这种测试的覆盖率极低上面说的 gap 更新位置错误就是被这种用例放过去的。一套靠谱的测试至少覆盖以下几类空数组和单元素数组验证边界不崩溃。已经有序的数组验证不会做多余操作同时结果不变。完全逆序的数组验证最坏情况下的正确性。包含重复元素的数组验证稳定性针对插入排序和正确性。随机大数组用标准库排序结果做对照。import random def test_sort(sort_func): cases [ [], [1], [1, 2, 3, 4, 5], [5, 4, 3, 2, 1], [3, 1, 3, 2, 1, 2], [random.randint(-100, 100) for _ in range(1000)], ] for case in cases: expected sorted(case) result sort_func(case[:]) # 传副本避免原地修改影响后续 assert result expected, ffailed on {case[:20]}... print(all passed)注意传副本这个细节。插入排序和希尔排序都是原地排序会修改传入的数组。如果测试时直接传原数组第一轮跑完数组已经被改了后面的对照就失去意义。用case[:]复制一份是最省事的做法。4.2 用“逆序对数量”观察希尔排序的中间过程想真正理解希尔排序为什么快可以加一段统计代码观察每轮 gap 之后数组的“逆序对”数量变化。逆序对就是前面比后面大的元素对数量越少说明数组越有序。def count_inversions(arr): cnt 0 for i in range(len(arr)): for j in range(i 1, len(arr)): if arr[i] arr[j]: cnt 1 return cnt def shell_sort_verbose(arr): n len(arr) gap n // 2 while gap 0: for i in range(gap, n): key arr[i] j i - gap while j 0 and arr[j] key: arr[j gap] arr[j] j - gap arr[j gap] key print(fgap{gap}, inversions{count_inversions(arr)}) gap // 2 return arr拿一个 16 元素的随机数组跑一下你会看到逆序对数量随着 gap 缩小快速下降到 gap1 之前通常已经降到个位数。这个观察比看十遍文字解释都管用因为它把“基本有序”这个抽象概念变成了具体数字。我在给团队新人讲希尔排序时都会让他们跑一遍这个统计跑完基本就没人再问“为什么希尔排序更快”了。4.3 性能实测什么规模下希尔排序开始碾压插入排序理论归理论实际跑一下更有说服力。下面这段代码对比两者在不同规模下的耗时import time def benchmark(n): data [random.randint(0, 10000) for _ in range(n)] t1 time.perf_counter() insertion_sort(data[:]) t2 time.perf_counter() shell_sort(data[:]) t3 time.perf_counter() print(fn{n}: insertion{t2-t1:.4f}s, shell{t3-t2:.4f}s) for size in [100, 500, 1000, 5000, 10000]: benchmark(size)实测下来具体数字因机器而异但趋势稳定n100 时两者差不多插入排序甚至可能略快因为希尔排序多了一层循环开销n500 时希尔排序开始领先n5000 时希尔排序通常快 5 到 10 倍n10000 时差距进一步拉大。这个拐点大致在几百的量级和前面说的“插入排序适合小规模”是吻合的。你可以用自己的机器跑一遍把拐点记下来以后选型时心里有数。5. 面试与工程中的高频追问5.1 “插入排序稳定希尔排序不稳定为什么”这是面试里区分“背过”和“真懂”的经典问题。插入排序稳定因为从后往前扫描时遇到相等元素就停下不会把后面的相等元素挪到前面去。希尔排序不稳定因为分组插入时相等的两个元素可能被分到不同的组各自组内排序后它们的相对位置可能颠倒。举个具体例子数组[2a, 2b, 1]其中 2a 和 2b 值相等但 2a 在前。假设 gap2分组为[2a, 1]和[2b]。第一组排序后变成[1, 2a]数组变成[1, 2b, 2a]。你看2a 和 2b 的相对顺序反了。这就是不稳定的根源——分组打破了原本的相邻关系。回答这个问题时能举出具体反例比干巴巴说“因为分组”有说服力得多。我建议把这个例子记牢面试时直接画出来。5.2 为什么很多库函数不用希尔排序标准库的排序实现比如常见的混合排序通常选择快排插入排序或者归并插入排序的组合很少用希尔排序。原因有几个第一希尔排序的最坏复杂度依赖增量序列不如快排的平均 O(n log n) 有保证第二希尔排序的缓存局部性不如快排——快排的分区操作访问的是连续内存希尔排序在大 gap 阶段跳跃访问缓存命中率低第三现代库更看重稳定性和可预测性希尔排序不稳定且性能对数据分布敏感。但这不代表希尔排序没用。在嵌入式、单片机、或者不允许递归和额外内存的场景里希尔排序原地、无递归、代码短的优势就体现出来了。选型从来不是选“最好的”而是选“最合适的”。5.3 增量序列能不能随便选最后一个必须是 1 的原因前面提过最后增量必须是 1这里展开说清楚。希尔排序的正确性依赖于当 gap1 时做一次完整的直接插入排序此时数组必须被完全排好。如果增量序列的最后一个值不是 1比如用了[4, 2]就结束了那么 gap2 的排序只能保证相隔 2 的元素有序相邻元素之间可能还是乱的整个数组不保证有序。数学上的解释是gap1 的插入排序是唯一能保证“任意相邻元素都有序”的步骤而“任意相邻元素有序”等价于“整个数组有序”。所以增量序列可以千变万化但收尾必须是 1。这个约束在自定义增量序列时千万不能忘我见过有人用质数序列[7,5,3]做增量忘了补 1结果排序结果部分正确排查了半天。5.4 实际项目里什么时候会真的手写这两个排序说实话业务代码里直接手写排序的场景不多标准库的sort基本够用。但有两种情况值得自己写一是数据规模极小且调用频繁比如每次只排 5 到 10 个元素的配置项标准库的通用排序有函数调用和类型检查开销手写插入排序反而更快二是排序逻辑需要嵌入到更大的算法里比如某些图算法需要对邻接表按权重排序数据量小且结构特殊内联一个插入排序比调库更自然。另外面试和算法题里这两个排序的出现频率很高尤其是“手写希尔排序”经常作为考察循环功底和边界处理的题目。把本文的代码模板和测试用例吃透这类题基本不会失分。6. 几个容易忽略的实操细节6.1 用 C 语言实现时的类型与越界问题Python 写起来舒服但很多场景要求 C 实现。C 版本有两个额外注意点一是key的类型要和数组元素类型一致如果数组是long long而key声明成int大数会被截断二是j的类型要用有符号整数如果用size_t无符号j - gap在j gap时会回绕成一个巨大的正数j 0永远成立直接死循环或者越界。void insertion_sort(int *arr, int n) { for (int i 1; i n; i) { int key arr[i]; int j i - 1; while (j 0 arr[j] key) { arr[j 1] arr[j]; j--; } arr[j 1] key; } }j用int而不是size_t这是 C 语言里处理“可能变成负数”的下标时的通用做法。如果数组长度可能超过int范围基本不可能但理论上才需要考虑long或ptrdiff_t。6.2 对链表做插入排序的思路差异数组的插入排序靠“挪动元素”链表的插入排序靠“改指针”。链表版本反而更自然维护一个已排序的子链表每次从未排序部分摘下一个节点遍历已排序部分找到插入位置改两个指针就完成了不需要挪动任何数据。这也是链表在插入场景下比数组有优势的地方。不过链表插入排序有个坑找插入位置时需要记录“前驱节点”因为单链表只能单向遍历找到位置后要修改前驱的next。如果插入到头部前驱为空需要单独处理。这个边界和数组版本里j1的统一处理不同链表版本通常要引入一个哑节点dummy head来消除头部特殊判断代码会干净很多。6.3 希尔排序在近乎有序数据上的表现反而可能不如插入排序这个结论有点反直觉但实测确实如此。如果数据已经基本有序直接插入排序几乎是 O(n) 一趟扫完而希尔排序不管数据什么样都要老老实实跑完所有 gap 轮次大 gap 阶段的跳跃访问反而做了无用功。所以如果你的业务场景里数据大概率已经有序比如增量更新的日志、追加写入的时间序列直接用插入排序别上希尔排序。判断方法很简单跑一次插入排序统计挪动次数如果挪动次数远小于 n²/4说明数据接近有序插入排序就是最优解。这个“先探测再选算法”的思路在性能敏感的场景里很实用。6.4 调试排序代码的三个高效手段最后分享几个我常用的调试技巧。第一打印每轮循环后的数组状态尤其是希尔排序的每个 gap 之后肉眼观察元素是否在往正确方向靠拢第二用极小的数组手动模拟比如 4 个元素拿纸笔跟着代码走一遍比盯着屏幕看有效得多第三构造针对性用例怀疑边界问题时用空数组和单元素怀疑稳定性时用带标记的重复元素比如(2,a)和(2,b)怀疑 gap 逻辑时用长度是 2 的幂的数组这样 gap 序列规整容易发现异常。这几个手段组合起来基本没有调不出来的排序 bug。排序算法的好处是结果可验证——和标准库对比一下就知道对不对所以调试的核心不是“找正确答案”而是“定位哪一步偏离了正确轨道”打印中间状态就是最直接的手段。
直接插入排序和希尔排序这两个东西放在排序算法家族里属于“看着简单、写起来容易翻车”的典型代表。很多人学排序的时候冒泡和选择排序过一遍就觉得自己懂了一到插入排序觉得“不就是往前面挪一挪嘛”结果真上手写代码边界条件一塌糊涂再往深了走到希尔排序增量序列怎么选、为什么它能比直接插入快、分组插入的循环到底怎么写一堆问号就冒出来了。我当年第一次手写希尔排序的时候外层循环的步长更新写错了位置跑出来的结果看着像排好了实际上部分元素根本没参与比较调了半天才定位到问题。这篇内容就是把我对这两个算法的理解、实操中踩过的坑、以及面试和工程里真正用得上的细节完整地摊开讲一遍。不管你是刚接触数据结构的学生还是工作几年想把基础重新夯实一遍的开发者都能从里面找到可以直接抄作业的代码模板和避坑清单。1. 先搞清楚这两个算法到底在解决什么问题1.1 从“整理扑克牌”说起插入排序的直觉来源直接插入排序的核心思想用生活场景解释最清楚你手里有一把扑克牌左手是已经理好的牌右手是还没理的牌。每次从右手抽一张插入到左手合适的位置左手始终保持有序。这个动作你打牌的时候做了无数遍根本不用想但翻译成代码就需要把“找位置”和“腾空间”这两件事拆开。具体到数组上我们把数组分成两部分前面一部分是已排序区间后面一部分是未排序区间。初始时已排序区间只有一个元素第一个元素天然有序然后每次取未排序区间的第一个元素在已排序区间里从后往前扫描找到合适位置插入进去同时把比它大的元素统统往后挪一位。这个过程重复到未排序区间为空整个数组就有序了。为什么是从后往前扫描而不是从前往后因为插入的同时需要腾位置。从后往前扫遇到比当前元素大的就往后挪一格挪到遇到比它小的或者到头了空出来的那个位置就是插入点。一趟扫描同时完成了“找位置”和“腾空间”不需要额外开数组空间复杂度是 O(1)。如果从前往后找位置找到之后还得把后面所有元素整体后移虽然结果一样但代码写起来别扭而且容易把下标搞乱。这里有个很多人忽略的细节插入排序是稳定排序。所谓稳定就是值相等的元素在排序后相对顺序不变。从后往前扫描时我们只在“严格大于”的时候才往后挪遇到相等就停下来插入这样相等元素的相对次序就保住了。这个性质在需要多关键字排序的场景里非常有用比如先按成绩排、再按姓名排稳定性保证了第二次排序不会打乱第一次的结果。1.2 希尔排序不是“另一种插入排序”而是插入排序的加速器很多人第一次看到希尔排序会觉得这是不是个完全不同的新算法。其实它的本质还是插入排序只不过做了一件很聪明的事先让数组变得“基本有序”再用直接插入排序收尾。直接插入排序有个致命弱点如果数组是逆序的比如[5,4,3,2,1]每次插入都要把前面所有元素挪一遍时间复杂度退化到 O(n²)。但如果数组本来就接近有序插入排序的效率极高接近 O(n)。希尔排序就是利用了这个特性——它先按一个较大的间隔增量把数组分成若干组对每组做插入排序。这时候元素可以“大步跳跃”地往正确位置靠拢而不是一步一步挪。随着增量逐渐缩小数组越来越有序最后增量变成 1做一次标准的直接插入排序此时数组已经基本有序这一趟几乎不需要挪动多少元素。打个比方直接插入排序像是每次只能挪一格搬家希尔排序像是先允许你跨楼层搬最后再在一层内微调。跨楼层搬的时候虽然看起来乱但大件家具很快就到了大致楼层最后微调的工作量就小得多。增量的选择是希尔排序的灵魂。最经典的是希尔增量n/2, n/4, n/8 ... 直到 1。这个序列简单好记但最坏情况下时间复杂度仍然是 O(n²)。后来有人提出了 Hibbard 增量1, 3, 7, 15...即 2^k - 1、Sedgewick 增量等更优的序列能把最坏复杂度降到 O(n^1.5) 甚至更好。实际工程中希尔增量因为实现简单、常数小在中等规模数据上表现并不差所以很多教材和面试题默认用它。1.3 两者的复杂度与适用场景对照把关键指标摆在一起看选择就清晰了对比维度直接插入排序希尔排序平均时间复杂度O(n²)取决于增量序列希尔增量为 O(n^1.5) 左右最坏时间复杂度O(n²)希尔增量下 O(n²)优化增量可改善最好时间复杂度O(n)已有序O(n log n) 量级空间复杂度O(1)O(1)稳定性稳定不稳定适用数据规模小规模n 100 左右中等规模几千到几万实现难度极低低但循环边界易错直接插入排序适合数据量小、或者数据已经基本有序的场景。很多标准库在数组长度小于某个阈值比如 16 或 32时会退化成插入排序因为小数组上它的常数因子比快排还小。希尔排序则适合中等规模、对稳定性没有要求、又不想引入递归或额外空间的场景比如嵌入式环境里对一段采集数据做排序。注意希尔排序是不稳定排序。分组插入的时候相等的元素可能被分到不同组相对顺序无法保证。如果业务要求稳定性老老实实用插入排序或者归并排序。2. 直接插入排序的代码骨架与边界陷阱2.1 一份可以直接背下来的标准实现先上代码用 Python 写因为它的列表操作直观换成 C/Java 逻辑完全一样def insertion_sort(arr): n len(arr) for i in range(1, n): key arr[i] j i - 1 while j 0 and arr[j] key: arr[j 1] arr[j] j - 1 arr[j 1] key return arr这段代码短到可以背下来但每一行都有讲究。i从 1 开始因为下标 0 的元素天然属于已排序区间。key保存当前要插入的元素这一步至关重要——如果不保存后面挪动元素的时候会把arr[i]覆盖掉数据就丢了。j从i-1开始往前扫while条件里j 0必须放在前面因为 Python 的and是短路求值如果先写arr[j] key当j变成 -1 时会访问arr[-1]在 Python 里这是最后一个元素逻辑直接错乱在 C/Java 里则直接数组越界崩溃。循环结束后j1就是插入位置。为什么是j1而不是j因为循环退出时要么j变成了 -1说明 key 比所有已排序元素都小应该插到最前面即下标 0正好是j1要么arr[j] key说明 key 应该插在j的后面也是j1。这个j1的统一性很多人第一次写会绕进去建议拿[3,1,2]手动走一遍。2.2 为什么 while 循环里必须先判断 j 的边界上面提到的短路求值问题值得单独拎出来说。我见过不少人在 C 语言里写成while (arr[j] key j 0) { ... }这在j变成 -1 的瞬间就会读取arr[-1]属于未定义行为可能读到垃圾值可能直接段错误。正确写法必须把边界判断放前面while (j 0 arr[j] key) { ... }这个顺序问题在 Python 里更隐蔽因为 Python 的负索引不会报错arr[-1]会悄悄返回最后一个元素导致排序结果看起来“差不多对”但个别元素位置错误排查起来极其痛苦。我建议养成肌肉记忆凡是往前扫描的循环边界判断永远写在条件最左边。2.3 用哨兵优化减少一次比较多数场景没必要有些教材会提到“哨兵”技巧把数组第 0 位留空存放当前要插入的元素作为哨兵这样 while 循环里就不用判断j 0了因为哨兵一定会在边界处停下来。这个技巧在 C 语言里能省一次比较理论上略微提升性能。但实际工程中我不推荐这么做。原因有三第一它要求数组从下标 1 开始存数据破坏了 0-based 的通用约定调用方容易踩坑第二省下的那次比较在现代 CPU 的分支预测面前收益微乎其微第三代码可读性下降维护成本上升。除非你在写对性能极度敏感的底层库否则标准写法完全够用。这个技巧知道有这么回事就行面试时提一嘴能加分实际项目里别给自己找麻烦。2.4 插入排序在真实代码里的“隐藏出场”插入排序最容易被低估的地方是它在工业级排序库里的角色。很多语言的标准库排序实现是混合策略大规模数据用快排或归并但当子数组长度小于某个阈值时切换到插入排序。原因是插入排序虽然渐近复杂度差但它的常数因子极小——没有递归调用开销、没有额外内存分配、循环体里就是简单的比较和赋值在小数组上跑得比快排还快。以常见的实现为例阈值通常设在 16 到 32 之间。这个数字不是拍脑袋定的而是实测出来的平衡点数组再大一点O(n²) 的劣势开始显现再小一点快排的递归开销占比过高。你在自己写排序工具时也可以借鉴这个思路比如对一个可能包含大量小分片的列表做排序先判断长度小于 20 就直接插入排序省去递归的麻烦。3. 希尔排序的增量逻辑与循环嵌套拆解3.1 从“分组”到“增量缩小”的完整推演希尔排序的代码比插入排序多一层循环但很多人卡在“到底哪层循环控制什么”上。我们一步步推。最外层是增量gap的递减循环从n//2开始每次减半直到gap 1。这一层决定了“分组的大小”。当gap 4时下标 0 和 4 是一组1 和 5 是一组以此类推每组内部做插入排序。中间层是i从gap遍历到n-1。为什么从gap开始因为每组的前gap个元素下标 0 到 gap-1分别是各组的第一个元素天然有序不需要处理。从gap开始每个元素都属于某个组需要往它所在组的前面插入。最内层就是标准的插入排序逻辑只不过往前扫描的步长是gap而不是 1。j从i-gap开始每次减gap比较和挪动都按gap的间隔进行。def shell_sort(arr): n len(arr) gap n // 2 while gap 0: for i in range(gap, n): key arr[i] j i - gap while j 0 and arr[j] key: arr[j gap] arr[j] j - gap arr[j gap] key gap // 2 return arr注意arr[j gap] arr[j]和最后的arr[j gap] key这里的gap对应插入排序里的1。因为挪动的步长是gap空出来的位置自然也是jgap。这个对应关系想通了希尔排序的代码就是插入排序把所有的1换成gap。3.2 增量序列的选择希尔增量不是唯一答案前面代码用的是希尔增量n/2 递减它简单但有个已知的弱点当gap较大时分组里元素少排序快但当gap缩小到某些值时可能出现“前面几轮白干了”的情况——某些元素在大的 gap 下被挪来挪去到了小的 gap 又被打回原形。最坏情况下复杂度仍是 O(n²)。如果想追求更好的性能可以换增量序列。Hibbard 增量是1, 3, 7, 15, ...通项是2^k - 1最坏复杂度 O(n^1.5)。Sedgewick 增量是1, 5, 19, 41, 109...最坏复杂度约 O(n^1.33)。实现上只需要把gap n//2; gap // 2换成预定义的序列倒序取用即可def shell_sort_hibbard(arr): n len(arr) gaps [] k 1 while (1 k) - 1 n: gaps.append((1 k) - 1) k 1 for gap in reversed(gaps): for i in range(gap, n): key arr[i] j i - gap while j 0 and arr[j] key: arr[j gap] arr[j] j - gap arr[j gap] key return arr实际选哪个我的经验是数据量在几千以内希尔增量和 Hibbard 增量实测差距不明显用希尔增量代码更短数据量上万且对性能有要求可以上 Hibbard 或 Sedgewick。但要注意增量序列的最后一个值必须是 1否则最后无法保证完全有序——这是硬性约束忘了就是逻辑错误。3.3 一个真实踩过的坑gap 更新位置写错导致“假排序”我第一次写希尔排序时把gap // 2写在了for i循环的内部结果每处理一个元素 gap 就减半循环提前结束数组只排了个大概。更坑的是测试用例用的是[3,1,2]这种小数组跑出来居然是对的直到换成[5,3,8,1,9,2,7,4,6]才暴露问题——部分元素根本没被比较到。这个坑的教训是gap 的更新必须在外层 while 循环的末尾等所有分组都处理完一轮之后才缩小。判断方法很简单在gap // 2那行打个断点或者打印一下看每轮 gap 的值是不是4, 2, 1这样递减如果看到4, 2, 1, 0中间夹杂着奇怪的数字就是位置写错了。还有一个隐蔽的变体错误while gap 0写成while gap 0当 gap 变成 0 时range(0, n)会正常执行但内层j i - 0 iarr[j0] arr[j]自己赋值给自己然后j - 0永远不变直接死循环。这个错误在 Python 里表现为程序卡死在 C 里也是死循环排查时容易误以为是数据量太大。记住gap 的终止条件是严格大于 0。4. 手写测试用例怎么验证你的排序真的对了4.1 别只用“看起来有序”的数组做测试很多人测试排序算法随手写个[3,1,2]跑一下输出[1,2,3]就认为对了。这种测试的覆盖率极低上面说的 gap 更新位置错误就是被这种用例放过去的。一套靠谱的测试至少覆盖以下几类空数组和单元素数组验证边界不崩溃。已经有序的数组验证不会做多余操作同时结果不变。完全逆序的数组验证最坏情况下的正确性。包含重复元素的数组验证稳定性针对插入排序和正确性。随机大数组用标准库排序结果做对照。import random def test_sort(sort_func): cases [ [], [1], [1, 2, 3, 4, 5], [5, 4, 3, 2, 1], [3, 1, 3, 2, 1, 2], [random.randint(-100, 100) for _ in range(1000)], ] for case in cases: expected sorted(case) result sort_func(case[:]) # 传副本避免原地修改影响后续 assert result expected, ffailed on {case[:20]}... print(all passed)注意传副本这个细节。插入排序和希尔排序都是原地排序会修改传入的数组。如果测试时直接传原数组第一轮跑完数组已经被改了后面的对照就失去意义。用case[:]复制一份是最省事的做法。4.2 用“逆序对数量”观察希尔排序的中间过程想真正理解希尔排序为什么快可以加一段统计代码观察每轮 gap 之后数组的“逆序对”数量变化。逆序对就是前面比后面大的元素对数量越少说明数组越有序。def count_inversions(arr): cnt 0 for i in range(len(arr)): for j in range(i 1, len(arr)): if arr[i] arr[j]: cnt 1 return cnt def shell_sort_verbose(arr): n len(arr) gap n // 2 while gap 0: for i in range(gap, n): key arr[i] j i - gap while j 0 and arr[j] key: arr[j gap] arr[j] j - gap arr[j gap] key print(fgap{gap}, inversions{count_inversions(arr)}) gap // 2 return arr拿一个 16 元素的随机数组跑一下你会看到逆序对数量随着 gap 缩小快速下降到 gap1 之前通常已经降到个位数。这个观察比看十遍文字解释都管用因为它把“基本有序”这个抽象概念变成了具体数字。我在给团队新人讲希尔排序时都会让他们跑一遍这个统计跑完基本就没人再问“为什么希尔排序更快”了。4.3 性能实测什么规模下希尔排序开始碾压插入排序理论归理论实际跑一下更有说服力。下面这段代码对比两者在不同规模下的耗时import time def benchmark(n): data [random.randint(0, 10000) for _ in range(n)] t1 time.perf_counter() insertion_sort(data[:]) t2 time.perf_counter() shell_sort(data[:]) t3 time.perf_counter() print(fn{n}: insertion{t2-t1:.4f}s, shell{t3-t2:.4f}s) for size in [100, 500, 1000, 5000, 10000]: benchmark(size)实测下来具体数字因机器而异但趋势稳定n100 时两者差不多插入排序甚至可能略快因为希尔排序多了一层循环开销n500 时希尔排序开始领先n5000 时希尔排序通常快 5 到 10 倍n10000 时差距进一步拉大。这个拐点大致在几百的量级和前面说的“插入排序适合小规模”是吻合的。你可以用自己的机器跑一遍把拐点记下来以后选型时心里有数。5. 面试与工程中的高频追问5.1 “插入排序稳定希尔排序不稳定为什么”这是面试里区分“背过”和“真懂”的经典问题。插入排序稳定因为从后往前扫描时遇到相等元素就停下不会把后面的相等元素挪到前面去。希尔排序不稳定因为分组插入时相等的两个元素可能被分到不同的组各自组内排序后它们的相对位置可能颠倒。举个具体例子数组[2a, 2b, 1]其中 2a 和 2b 值相等但 2a 在前。假设 gap2分组为[2a, 1]和[2b]。第一组排序后变成[1, 2a]数组变成[1, 2b, 2a]。你看2a 和 2b 的相对顺序反了。这就是不稳定的根源——分组打破了原本的相邻关系。回答这个问题时能举出具体反例比干巴巴说“因为分组”有说服力得多。我建议把这个例子记牢面试时直接画出来。5.2 为什么很多库函数不用希尔排序标准库的排序实现比如常见的混合排序通常选择快排插入排序或者归并插入排序的组合很少用希尔排序。原因有几个第一希尔排序的最坏复杂度依赖增量序列不如快排的平均 O(n log n) 有保证第二希尔排序的缓存局部性不如快排——快排的分区操作访问的是连续内存希尔排序在大 gap 阶段跳跃访问缓存命中率低第三现代库更看重稳定性和可预测性希尔排序不稳定且性能对数据分布敏感。但这不代表希尔排序没用。在嵌入式、单片机、或者不允许递归和额外内存的场景里希尔排序原地、无递归、代码短的优势就体现出来了。选型从来不是选“最好的”而是选“最合适的”。5.3 增量序列能不能随便选最后一个必须是 1 的原因前面提过最后增量必须是 1这里展开说清楚。希尔排序的正确性依赖于当 gap1 时做一次完整的直接插入排序此时数组必须被完全排好。如果增量序列的最后一个值不是 1比如用了[4, 2]就结束了那么 gap2 的排序只能保证相隔 2 的元素有序相邻元素之间可能还是乱的整个数组不保证有序。数学上的解释是gap1 的插入排序是唯一能保证“任意相邻元素都有序”的步骤而“任意相邻元素有序”等价于“整个数组有序”。所以增量序列可以千变万化但收尾必须是 1。这个约束在自定义增量序列时千万不能忘我见过有人用质数序列[7,5,3]做增量忘了补 1结果排序结果部分正确排查了半天。5.4 实际项目里什么时候会真的手写这两个排序说实话业务代码里直接手写排序的场景不多标准库的sort基本够用。但有两种情况值得自己写一是数据规模极小且调用频繁比如每次只排 5 到 10 个元素的配置项标准库的通用排序有函数调用和类型检查开销手写插入排序反而更快二是排序逻辑需要嵌入到更大的算法里比如某些图算法需要对邻接表按权重排序数据量小且结构特殊内联一个插入排序比调库更自然。另外面试和算法题里这两个排序的出现频率很高尤其是“手写希尔排序”经常作为考察循环功底和边界处理的题目。把本文的代码模板和测试用例吃透这类题基本不会失分。6. 几个容易忽略的实操细节6.1 用 C 语言实现时的类型与越界问题Python 写起来舒服但很多场景要求 C 实现。C 版本有两个额外注意点一是key的类型要和数组元素类型一致如果数组是long long而key声明成int大数会被截断二是j的类型要用有符号整数如果用size_t无符号j - gap在j gap时会回绕成一个巨大的正数j 0永远成立直接死循环或者越界。void insertion_sort(int *arr, int n) { for (int i 1; i n; i) { int key arr[i]; int j i - 1; while (j 0 arr[j] key) { arr[j 1] arr[j]; j--; } arr[j 1] key; } }j用int而不是size_t这是 C 语言里处理“可能变成负数”的下标时的通用做法。如果数组长度可能超过int范围基本不可能但理论上才需要考虑long或ptrdiff_t。6.2 对链表做插入排序的思路差异数组的插入排序靠“挪动元素”链表的插入排序靠“改指针”。链表版本反而更自然维护一个已排序的子链表每次从未排序部分摘下一个节点遍历已排序部分找到插入位置改两个指针就完成了不需要挪动任何数据。这也是链表在插入场景下比数组有优势的地方。不过链表插入排序有个坑找插入位置时需要记录“前驱节点”因为单链表只能单向遍历找到位置后要修改前驱的next。如果插入到头部前驱为空需要单独处理。这个边界和数组版本里j1的统一处理不同链表版本通常要引入一个哑节点dummy head来消除头部特殊判断代码会干净很多。6.3 希尔排序在近乎有序数据上的表现反而可能不如插入排序这个结论有点反直觉但实测确实如此。如果数据已经基本有序直接插入排序几乎是 O(n) 一趟扫完而希尔排序不管数据什么样都要老老实实跑完所有 gap 轮次大 gap 阶段的跳跃访问反而做了无用功。所以如果你的业务场景里数据大概率已经有序比如增量更新的日志、追加写入的时间序列直接用插入排序别上希尔排序。判断方法很简单跑一次插入排序统计挪动次数如果挪动次数远小于 n²/4说明数据接近有序插入排序就是最优解。这个“先探测再选算法”的思路在性能敏感的场景里很实用。6.4 调试排序代码的三个高效手段最后分享几个我常用的调试技巧。第一打印每轮循环后的数组状态尤其是希尔排序的每个 gap 之后肉眼观察元素是否在往正确方向靠拢第二用极小的数组手动模拟比如 4 个元素拿纸笔跟着代码走一遍比盯着屏幕看有效得多第三构造针对性用例怀疑边界问题时用空数组和单元素怀疑稳定性时用带标记的重复元素比如(2,a)和(2,b)怀疑 gap 逻辑时用长度是 2 的幂的数组这样 gap 序列规整容易发现异常。这几个手段组合起来基本没有调不出来的排序 bug。排序算法的好处是结果可验证——和标准库对比一下就知道对不对所以调试的核心不是“找正确答案”而是“定位哪一步偏离了正确轨道”打印中间状态就是最直接的手段。
