我可以先给个结论：希尔排序是那种“看起来是插入排序的魔改版，实际上讲究却很多”的算法。你如果已经会写插入排序，再看希尔排序的代码会觉得特别眼熟，可一旦被问到“为什么分组之后能变快”这类原理题，很多人又说不清楚。这篇文章我会从设计思路讲起，把增量序列、代码写法、复杂度结论和常见的坑一次讲透，再给两个能直接运行的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，完成最后一次普通插入排序。
这里的“分组”不是真的把数组拆开再拼回去，元素仍然在同一个数组里，只是按索引的间隔来划分。比如数组长度是 8，gap = 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 | 模拟分组情况 | 排序后数组 |
|---|---|---|---|
| 1 | 4 | [13,12] [5,3] [9,7] [2,1] | [12, 3, 7, 1, 13, 5, 9, 2] |
| 2 | 2 | [12,7,13,9] [3,1,5,2] | [7, 1, 9, 2, 12, 3, 13, 5] |
| 3 | 1 | 全数组插入排序 | [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只是用来区分三个相同的5），gap = 3 时第一组是[5a, 1, 5c]，排序后变成[1, 5a, 5c]；但此时第二组[2, 3]保持不变，合并后数组变成[1, 2, 5b, 5a, 5c, 3]。原本 5a 在 5b 前面，现在 5b 跑到前面去了，相等元素的相对顺序被破坏。
再说最坏情况。如果你用一个不太合理的增量序列，比如 gap 从 1 开始递增而不是递减，或者 gap 序列没有覆盖到 1，结果都会出问题。标准实现里最后一定要做 gap=1 的那一轮，否则数组可能根本没有完全有序。
顺便提一句，复杂度的分析之所以绕，是因为增量序列的选择直接影响每一轮的分组方式和组内排序成本。目前没有一个对所有增量序列都成立的统一简洁公式，所以很多教材会直接给出经验结论。面试时能说出“复杂度取决于 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 面试官常问的几个问题怎么答
面试里关于希尔排序的问题，翻来覆去基本就是这几类。我按我的理解给一个答题思路。
第一个问题：为什么最后一定要做 gap=1 的排序？因为前面的所有分组排序都只是让数组“趋于有序”，只有 gap=1 才能覆盖到所有相邻元素，保证任意两个元素之间都不再存在逆序对。如果提前退出，数组可能仍然不是全序。
第二个问题：希尔排序稳定吗？不稳定。理由就是刚才讲过的跳跃移动会破坏相等元素的相对顺序，举一个小例子说明即可。
第三个问题：希尔排序和插入排序是什么关系？希尔排序可以看作是插入排序的推广：当 gap=1 时，希尔排序就是普通插入排序；当 gap>1 时，每个分组内部的排序逻辑和插入排序完全一致，只是跳跃步长不同。
第四个问题：它的最坏复杂度是多少？要回答“取决于增量序列”，然后补充一句：折半递减序列的最坏复杂度和普通插入排序一样都可能退化为 O(n²)，但使用一些精心设计的增量序列，可以控制到更低的上界。这个回答会明显比只背一个“O(n log n)”更有说服力。
如果面试官继续追问复杂度的推导细节，可以坦诚说希尔排序的复杂度分析依赖于增量序列，数学工具比较复杂，但你能说出关键结论就足够了。面试考这个算法，更多是想看你对排序本质的理解，而不是让你证明复杂度的上界。
4.3 优化方向和实际应用场景
希尔排序的优化方向主要还是集中在增量序列上。折半递减虽然简单，但不一定能带来理论最优表现；换成类似Sedgewick序列、在数学上被证明更优的序列，可以在随机数据上获得更好的性能。另一类优化是把最后一轮换成其他排序，比如当 gap 缩小到某个阈值后直接调用普通插入排序，这样能减少外层多次分组的开销。
但在 Python 语境下，我建议对希尔排序的定位要摆正：它更多是教学和思维训练工具，而不是用来挑战内置排序。Python 的sorted()和列表的sort()方法实现非常成熟，遇到真实业务场景直接用它们就好。希尔排序具有 O(1) 空间复杂度，这决定了它适合在某些内存极度受限的环境中作为一种折中方案，不过这种场景在现代开发里越来越少。
如果你想做一点有趣的实验，可以在希尔排序的间隙“混合”其他策略，比如 gap 较大时先不排序，而是做一趟快速分组；或者在小数组上改用直接插入排序。这会打破“排序算法就是标准模板”的固有印象，也能帮你更深入理解排序过程本身。
我自己实际跑下来，最大的体会是希尔排序非常适合用来训练“通过改变步长来改变算法行为”的思维。平时写代码时，我们总觉得循环就是从一头走到另一头；希尔排序告诉你，索引间隔本身就是一种可以动态调整的资源。对初学者来说，在纸上画一个 8 元素数组，把 gap 从 4 改成 2 再改成 1，手动演算三轮，比看十遍代码都有效。遇到笔试里的希尔排序题，只要记得“先粗排、再细排”和“最后一轮 gap 必须是 1”，至少不会被最基本的边界条件坑到。
