我可以先给个结论希尔排序是那种“看起来是插入排序的魔改版实际上讲究却很多”的算法。你如果已经会写插入排序再看希尔排序的代码会觉得特别眼熟可一旦被问到“为什么分组之后能变快”这类原理题很多人又说不清楚。这篇文章我会从设计思路讲起把增量序列、代码写法、复杂度结论和常见的坑一次讲透再给两个能直接运行的Python示例。适合准备技术笔试、面试的人也适合想真正把排序算法原理吃透的初学者。先解释一个最简单的直觉插入排序慢在逆序多的时候每个元素都得一步一步挪到自己该去的位置。希尔排序的思路就是在做插入排序之前先用较大的间隔把元素归到大致正确的位置最后再做一次间隔为1的普通插入排序。这个“先粗排、再细排”的过程就是“缩小增量排序”的核心。1. 希尔排序是怎么一步步设计出来的从插入排序到分组跳跃1.1 插入排序的软肋为什么逆序数据会让它很吃力插入排序的算法逻辑很直白从左到右依次处理每个元素把它插入到左侧已经有序的序列里。如果输入数组差不多已经有序那么每个元素只需要比较一两次就能找到位置整个排序接近 O(n)但如果输入是完全逆序的比如[9, 8, 7, 6, 5, 4, 3, 2, 1]那么最后一个元素要一直挪到最前面这个搬运过程要重复很多次。排序的开销其实可以拆成两块一块是比较次数另一块是元素移动次数。对插入排序来说逆序数据会让每插入一个新元素时前面所有比它大的元素都得往后移一位。这个移动量合起来就是 n(n-1)/2 的量级也就是 O(n²)。数据一到了几千上万的规模这种“一格一格挪”的代价就很明显了。我经常把插入排序类比成手工整理一摞文件如果只有一两份文件放错位置你很快就能处理完但如果一整摞文件全部是倒序的你每拿起一份新文件都要把前面一堆文件重新挪一遍。人会很自然地想到先按大类别分堆再在小堆里微调希尔排序其实也是这个思路。1.2 分组跳跃的思路引入gap来解决“一次只挪一步”希尔排序的核心动作是引入一个间隔一般记作 gap。它会先把数组里所有“相隔 gap 个位置”的元素当作一个小组对每个小组做一次插入排序然后把 gap 缩小再分组、再插入排序不断重复直到 gap 变成 1完成最后一次普通插入排序。这里的“分组”不是真的把数组拆开再拼回去元素仍然在同一个数组里只是按索引的间隔来划分。比如数组长度是 8gap 2那索引 0、2、4、6 算一组索引 1、3、5、7 算一组。对每一组分别进行插入排序时组内元素一次可以跳过 gap 个位置而不是像普通插入排序那样一次只能挪一格。这样做的直接好处是让某个离目标位置很远的元素能快速前进一大段距离。比如一个数值很小的元素待在数组末尾gap 4 的时候它一次就能向前跳 4 格进入正确的分区要是用普通插入排序它可能要经过很多次相邻交换才能到达位置。也就是说大 gap 负责解决“整体宏观乱序”后面小 gap 负责解决“局部微观乱序”。到 gap 1 时数组已经处于“基本有序”的状态了这时候再做一次完整插入排序需要的比较和移动都很少。整个排序的总消耗自然就降了下来。1.3 为什么这种粗排再加细排会更快换个角度看逆序对要真正理解希尔排序的效率最好引入“逆序对”这个概念。逆序对就是数组中一对索引 i j 但数值 A[i] A[j] 的元素。插入排序每交换一次相邻元素最多只能消除一个逆序对如果数组里逆序对很多排序需要执行的交换就非常多。希尔排序在做大 gap 分组插入排序时组内元素会跳跃式移动一次交换就可能消掉多个逆序对因为元素一下跨过了好几个位置。这样经过几轮粗排数组里的逆序对总量已经大幅减少最后一轮插入排序的工作量也就不大了。我自己的理解方式是这样的普通插入排序是“就近解决问题”每次只把眼前的小混乱整理好希尔排序是“先解决问题的主要矛盾”用大间隔把数据大幅度靠近最终位置再逐步精确化。这也是为什么它会被称为“缩小增量排序”而不是“跳跃排序”因为增量逐渐变小排序粒度逐渐变细。2. 希尔排序核心原理与Python代码逐步解析2.1 增量序列gap到底该取多少gap 怎么选直接决定了希尔排序的性能表现。最简单也最常见的做法是gap n // 2然后每轮gap // 2一直到 1。这个方案优点是代码简单大多数情况下表现也不错缺点是有理论分析指出它并不能保证在所有数据上都达到理想复杂度最坏情况下仍然可能退化到 O(n²)。还有两种在算法资料里经常被提到的增量序列。一种是类似2^k - 1的序列比如 1、3、7、15……一些资料里叫它Hibbard序列另一种是兼顾奇偶分布、在一些场景下表现更稳的Sedgewick序列比如9 * 4^j - 9 * 2^j 1。这些序列的复杂度分析更复杂但思路都是一样的让 gap 的递减不要那么“平缓”尽可能避免最坏情况。对日常学习和工程演示来说折半递减的 gap 已经足够。因为希尔排序在 Python 里并不会竞争内置排序函数它更大的价值是帮助理解算法设计中的“分阶段调整”思想。所以不要纠结序列的数学推导先把 gap 不断缩小的逻辑掌握好。我见过有人直接写gap // 2之后发现第二轮 gap 变成 0然后整个排序提前结束。这个问题的根源在于把整数除法写成了浮点除法或者循环条件判断写反了。稍后我会在问题排查部分详细说明。2.2 最经典的原地排序写法逐行拆解下面这段是希尔排序非常经典的 Python 实现也是网上和教材里最常见的一种。我先放完整代码再逐行解释关键点。def shell_sort(arr): n len(arr) gap n // 2 while gap 0: for i in range(gap, n): tmp arr[i] j i while j gap and arr[j - gap] tmp: arr[j] arr[j - gap] j - gap arr[j] tmp gap // 2 return arr先看外层结构gap n // 2是初始间隔while gap 0保证最后一轮会把 gap 缩到 1然后处理完退出。每一轮结束用gap // 2缩小间隔这里必须用整数除法不然下一轮 gap 会变成小数。再看中间的for i in range(gap, n)。它不是在按“组”处理而是从第 gap 个元素开始逐个把元素当成“当前要插入到前方序列中的对象”。由于 gap 正好分开的是同一组元素从 gap 位置开始遍历能保证每一组内部的插入操作都被覆盖到。内层的while循环就是一次带间隔的插入排序tmp保存当前元素j从当前位置往前跳每次比较arr[j - gap]和tmp。如果前面的元素更大就把它往后挪 gap 个位置一直挪到前方没有更大元素或者已经到数组边界为止最后把tmp放回正确位置。很多人会在这里把条件误写成j 0。表面上看没什么问题但在 Python 里arr[-1]是可以访问的它代表的是数组最后一个元素而不是报错。一旦内层循环多了这次负索引比较排序结果就会出现非常诡异的错误而且很难通过肉眼排查。所以要记住这里的while j gap不是在偷懒而是为了保证arr[j - gap]一定存在。这个边界条件极其重要。2.3 我建议初学者先读一遍的“按组处理”版本上面那种写法代码短、执行效率高但思路不够直白。如果你第一次接触希尔排序很可能看不懂为什么for i in range(gap, n)就能把那么多组都排好。这里我提供一个更贴近“分组排序”字面意思的写法逻辑上更直观。def shell_sort_group(arr): n len(arr) gap n // 2 while gap 0: for start in range(gap): for i in range(start gap, n, gap): tmp arr[i] j i while j gap and arr[j - gap] tmp: arr[j] arr[j - gap] j - gap arr[j] tmp gap // 2 return arr这个版本的外层for start in range(gap)是在枚举每一组的开头中间的for i in range(start gap, n, gap)是在同一组内做普通插入排序。你可以把它理解为先把数组切成若干条“子序列”再对每个子序列独立排序。这和第一个版本做的事情本质上是相同的只是多了一层循环改成用 Python 的 range 显式管理步长。两个版本对比着看你会发现第一个版本实际上是把“按组遍历”和“插入排序”合并在一起了所以代码更精炼。第二个版本在初学者理解阶段更友好但多了一层 Python for 循环运行时会慢一些。我建议学习时先用第二个版本搞清楚逻辑再去看第一个版本这样面试时不管看到哪种写法都不会懵。3. 跑一遍希尔排序完整示例、复杂度与测试脚本3.1 用8个元素的数组完整演算一轮抽象描述再多不如跑一个具体例子。我用[13, 5, 9, 2, 12, 3, 7, 1]来走一遍数组长度 n 8初始 gap 4。第一轮 gap 4。分组如下索引 0 和 4 是一组对应[13, 12]索引 1 和 5 是一组对应[5, 3]索引 2 和 6 是一组对应[9, 7]索引 3 和 7 是一组对应[2, 1]。每组分别排序后数组变成[12, 3, 7, 1, 13, 5, 9, 2]。注意这轮只是让两两元素相对有序并没有完全排好。第二轮 gap 2。此时数组按间隔 2 分成两组索引 0、2、4、6 是[12, 7, 13, 9]索引 1、3、5、7 是[3, 1, 5, 2]。对这两个子序列分别做插入排序第一组变成[7, 9, 12, 13]第二组变成[1, 2, 3, 5]合并回去得到[7, 1, 9, 2, 12, 3, 13, 5]。第三轮 gap 1这就相当于一次普通插入排序。对整个数组排序后得到[1, 2, 3, 5, 7, 9, 12, 13]。整理成表格更清楚轮次gap模拟分组情况排序后数组14[13,12] [5,3] [9,7] [2,1][12, 3, 7, 1, 13, 5, 9, 2]22[12,7,13,9] [3,1,5,2][7, 1, 9, 2, 12, 3, 13, 5]31全数组插入排序[1, 2, 3, 5, 7, 9, 12, 13]从这张表你可以直观看到前两轮虽然没有让整个数组完全有序但明显已经把小数往前推、大数往后移了最后一轮的工作量变得非常小。这就是希尔排序的核心体验。3.2 复杂度、稳定性与最坏情况别被“看起来像插入排序”骗了希尔排序的复杂度不能简单用一个公式说死因为不同的增量序列会得到不同的理论结论。如果使用经典的折半递减间隔工程上一般认为指标结论说明最好情况接近 O(n)甚至接近 O(n log n)数据基本有序时表现很好平均情况大约 O(n^1.3) 到 O(n^1.5)依赖增量序列不是一个统一数值最坏情况O(n²)gap 序列不合适时可能退化空间复杂度O(1)原地排序不需要额外数组稳定性不稳定跳跃移动会破坏相等元素的原始顺序先说稳定性。为什么希尔排序不稳定因为大 gap 分组时两个相等元素可能位于不同的分组排序过程中某个元素会跨过另一个相等元素造成相对位置变化。举个简单例子数组[5a, 2, 5b, 1, 5c, 3]a、b、c只是用来区分三个相同的5gap 3 时第一组是[5a, 1, 5c]排序后变成[1, 5a, 5c]但此时第二组[2, 3]保持不变合并后数组变成[1, 2, 5b, 5a, 5c, 3]。原本 5a 在 5b 前面现在 5b 跑到前面去了相等元素的相对顺序被破坏。再说最坏情况。如果你用一个不太合理的增量序列比如 gap 从 1 开始递增而不是递减或者 gap 序列没有覆盖到 1结果都会出问题。标准实现里最后一定要做 gap1 的那一轮否则数组可能根本没有完全有序。顺便提一句复杂度的分析之所以绕是因为增量序列的选择直接影响每一轮的分组方式和组内排序成本。目前没有一个对所有增量序列都成立的统一简洁公式所以很多教材会直接给出经验结论。面试时能说出“复杂度取决于 gap 序列”这句话其实已经比很多背教材的人更深入了。3.3 可以直接复用的调试脚本和性能对比学习阶段最重要的事情是看到排序的中间过程。我给希尔排序加个调试版本方便观察每一轮的变化。def shell_sort_debug(arr): n len(arr) gap n // 2 step 1 while gap 0: for i in range(gap, n): tmp arr[i] j i while j gap and arr[j - gap] tmp: arr[j] arr[j - gap] j - gap arr[j] tmp print(f第{step}轮: gap{gap}, arr{arr}) gap // 2 step 1 return arr运行shell_sort_debug([13, 5, 9, 2, 12, 3, 7, 1])你会在控制台看到每一轮之后数组的变化这比自己脑补要直观得多。真遇到 bug把这种带日志的版本跑一遍往往几秒钟就能定位问题。想对比性能和内置排序可以参考下面这段脚本import random import time data [random.randint(0, 10000) for _ in range(3000)] data_copy data[:] start time.perf_counter() shell_sort(data) print(希尔排序耗时:, time.perf_counter() - start) start time.perf_counter() sorted(data_copy) print(Python内置排序耗时:, time.perf_counter() - start)有一点要注意改用纯插入排序和希尔排序对比时不要选 10000 个全逆序元素否则插入排序会非常慢。我自己试过几千规模就能看到差距规模太小时函数调用和循环开销又会干扰对比结果。做性能实验时保持“同一份数据、同一种环境、重复多次取平均”才是正确姿势。4. 希尔排序常见报错、面试考点与优化方向4.1 新手最容易踩的5个坑写希尔排序的代码量不大但细节极其容易出错。我根据自己看到的和踩过的坑整理成一张速查表常见问题现象原因分析和解决方案gap 变成 0 导致最后一轮缺失排序结果不全有序用了浮点除法或循环条件写错。确保gap // 2并且while gap 0内层条件写成 j 0结果错得莫名其妙Python 负索引不会报错会把数组末尾元素纳入比较。必须写成j gap认为必须先拆分数组理解混乱代码写得很复杂希尔排序的逻辑分组不改变物理顺序所有操作都在原数组上完成相等元素顺序变了当成 bug调试很久找不到问题这不是代码错误是不稳定排序特性数据量大时比内置排序慢结果正确但性能不佳希尔排序在纯算法练习里很有价值日常工程直接用内置排序即可这里我想特别强调负索引这个坑。Python 的arr[-1]是合法访问不像很多其他语言会直接报数组越界。所以当你在while条件里不小心写成j 0并访问arr[j - gap]其中j - gap可能是负数程序不会马上崩而是拿最后一个元素来比较。这种 bug 非常隐蔽不如越界报错那么显眼。4.2 面试官常问的几个问题怎么答面试里关于希尔排序的问题翻来覆去基本就是这几类。我按我的理解给一个答题思路。第一个问题为什么最后一定要做 gap1 的排序因为前面的所有分组排序都只是让数组“趋于有序”只有 gap1 才能覆盖到所有相邻元素保证任意两个元素之间都不再存在逆序对。如果提前退出数组可能仍然不是全序。第二个问题希尔排序稳定吗不稳定。理由就是刚才讲过的跳跃移动会破坏相等元素的相对顺序举一个小例子说明即可。第三个问题希尔排序和插入排序是什么关系希尔排序可以看作是插入排序的推广当 gap1 时希尔排序就是普通插入排序当 gap1 时每个分组内部的排序逻辑和插入排序完全一致只是跳跃步长不同。第四个问题它的最坏复杂度是多少要回答“取决于增量序列”然后补充一句折半递减序列的最坏复杂度和普通插入排序一样都可能退化为 O(n²)但使用一些精心设计的增量序列可以控制到更低的上界。这个回答会明显比只背一个“O(n log n)”更有说服力。如果面试官继续追问复杂度的推导细节可以坦诚说希尔排序的复杂度分析依赖于增量序列数学工具比较复杂但你能说出关键结论就足够了。面试考这个算法更多是想看你对排序本质的理解而不是让你证明复杂度的上界。4.3 优化方向和实际应用场景希尔排序的优化方向主要还是集中在增量序列上。折半递减虽然简单但不一定能带来理论最优表现换成类似Sedgewick序列、在数学上被证明更优的序列可以在随机数据上获得更好的性能。另一类优化是把最后一轮换成其他排序比如当 gap 缩小到某个阈值后直接调用普通插入排序这样能减少外层多次分组的开销。但在 Python 语境下我建议对希尔排序的定位要摆正它更多是教学和思维训练工具而不是用来挑战内置排序。Python 的sorted()和列表的sort()方法实现非常成熟遇到真实业务场景直接用它们就好。希尔排序具有 O(1) 空间复杂度这决定了它适合在某些内存极度受限的环境中作为一种折中方案不过这种场景在现代开发里越来越少。如果你想做一点有趣的实验可以在希尔排序的间隙“混合”其他策略比如 gap 较大时先不排序而是做一趟快速分组或者在小数组上改用直接插入排序。这会打破“排序算法就是标准模板”的固有印象也能帮你更深入理解排序过程本身。我自己实际跑下来最大的体会是希尔排序非常适合用来训练“通过改变步长来改变算法行为”的思维。平时写代码时我们总觉得循环就是从一头走到另一头希尔排序告诉你索引间隔本身就是一种可以动态调整的资源。对初学者来说在纸上画一个 8 元素数组把 gap 从 4 改成 2 再改成 1手动演算三轮比看十遍代码都有效。遇到笔试里的希尔排序题只要记得“先粗排、再细排”和“最后一轮 gap 必须是 1”至少不会被最基本的边界条件坑到。
