排序算法学到最后你会发现，真正“通吃所有场景”的算法几乎不存在，反而是各种带条件的选手各显身手。希尔排序就是其中一个有意思的中间派：它比插入排序快不少，又比快速排序、归并排序容易理解得多，而且完全不占用额外内存。如果你写过几行 Python，多半听说过它，但可能一直没搞明白“分组插入”到底怎么分组、步长序列又是什么、为什么这样做能变快。这篇文章我把希尔排序的原理拆开讲透，给出可以直接跑的完整示例代码，再聊聊实际排序时怎么选步长、会遇到哪些坑。适合刚学完插入排序、想提升一点性能的人，也适合面试前想快速理顺思路的开发者。
1. 插入排序的瓶颈与希尔排序的破局思路
1.1 插入排序为什么在大乱序面前会拖后腿
插入排序的思路非常简单：维护一个左侧的有序区，从右侧取出一个元素，在有序区里从右往左找位置，把它插进去。数据量小、数据本身接近有序的时候，它非常快，最好情况就是 O(n)，这也是为什么很多高级排序在小规模数据上会回退到插入排序。
但它有一个致命问题：在乱序大数组上，每个新元素可能要从右侧一路挪到接近最左侧，一次只能相邻交换一格。看成百上千个元素“一格一格往左爬”，比较和赋值的次数一下子就上来了。平均时间复杂度和最坏时间复杂度都是 O(n²)，数据量一上万，肉眼就能感觉到卡顿。
想象一下整理书架的场景：把几百本书彻底打乱，然后一本一本地按相邻位置找正确位置，每本书都要从当前位置一格一格挪过去，确实很折磨。如果先把书架分成好几组，每组内部快速整理一遍，再逐步缩小分组范围，最后整体整理，整个过程会省力很多。希尔排序的出发点正是这个直觉。
1.2 核心直觉：先大步跨越，再小步微调
希尔排序对数组做的事，可以概括成一句话：按一定间隔 gap 把数组拆成多个子序列，分别对每个子序列做插入排序，然后不断缩小 gap，直到 gap 等于 1，做最后一次完整插入排序。
关键在于，当 gap 比较大的时候，元素可以一次跳很远。原本要挪很多轮的位置，现在几步就能靠近最终区域。已经完成“宏观归位”之后，再缩小 gap 做精细调整，最后 gap=1 时数组已经相当接近有序，插入排序的快特性就能发挥出来。
我给你模拟一个小数组的过程。假设有数组：
[9, 8, 7, 6, 5, 4, 3, 2, 1]取 gap = 4 时，它被分成 4 组：
第1组：9, 5, 1 第2组：8, 4 第3组：7, 3 第4组：6, 2分别对每一组做插入排序后，整体变成：
[1, 4, 3, 2, 5, 8, 7, 6, 9]仔细看，原先最大的 9 已经一步跳到末尾附近，原先最小的 1 也一步跳到开头附近。这就是“跨越式移动”的价值。如果换成普通插入排序，9 要从第二位一路比到末尾，需要比较 8 次。现在分组操作大大减少了这种长距离搬运。
随后把 gap 缩小到 2、1，逐步微调，整体排序完成的代价远低于直接插入排序。这也是希尔排序在一些老教材里被叫作“缩小增量排序”的原因。
2. 增量序列的选择：不同步长策略对性能的影响
2.1 为什么 gap 不能直接从 1 开始
如果你写一个排序函数，gap 一开始就取 1，那整个算法退化成普通插入排序，分组的意义完全丧失。希尔排序想要快，关键就是先让 gap 取一个比较大的值，让元素跨组移动，最后才用 gap=1 收尾。
那 gap 应该从多大开始？常见做法是从数组长度的一半或者某种递减公式开始，逐步缩小。从最大步长到最终步长 1 组成的整个序列，就是增量序列，也叫步长序列。
一个值得注意的问题是：并不是 gap 从大到小随便取都能保证最后得到正确结果。排序过程即使中间分组的“动静”很大，只要最后一次 gap=1 做的是完整插入排序，就一定能把数组排好。步长序列真正影响的是“中间过程对最后一步的帮助有多大”，也就是性能差异的主要来源。
2.2 几种常见增量序列对比
增量序列的方案其实有不少，下面列几个比较常用的。
| 增量序列方案 | 生成方式 | 典型最坏时间复杂度 | 特点 |
|---|---|---|---|
| 折半递减 | gap = n // 2，每次 gap //= 2 | O(n²) | 实现简单，最常见 |
| 2^k - 1 形式 | 从 1 开始，按 2^k - 1 生成并逆序使用 | 约 O(n^(3/2)) | 组间碰撞更少，平均表现更好 |
| 3^k + 1 形式 | 从 1 开始，按 3^k + 1 生成并逆序使用 | 约 O(n^(3/2)) | 没有 2 和 3 的整倍数公因子，据说效果均衡 |
| 混合序列 | 直接给定一组经验步长，比如从 1 开始，逆序使用 | 不同数据表现不同 | 更灵活，但需要针对数据调参 |
折半递减是最常见的教学实现，因为它最符合直觉：每次把数组分成两半，迭代下去。但某些极端数据下，一批元素可能要反复跨组调整，表现并不算最优。像 2^k - 1 这种互相之间没有共同因子的步长，会让后续几次分组不完全重叠，从而减少“补课”式的重复比较。
需要说明的是，如果目标是把数组排成有序结果，任何一组最终包含 1 的步长序列都不会让排序失效。步长序列的差异更多体现在耗时和比较次数上，是性能优化层面的问题。
2.3 步长序列影响排序速度的底层逻辑
先想清楚一次插入排序的成本：它实际上取决于每个元素往前移动的总距离。gap 大时，每个子序列的长度很短，虽然单个元素移动跨度大，但参与比较的元素总量少，总代价可控。gap 逐渐变小时，虽然每个子序列变长了，但数据经过前面几轮“宏观调整”，已经接近有序，每个元素的移动距离很小。
如果选择的步长序列不够好，就可能出现“前一轮刚把某些元素按一种方式分组排好，下一轮分组又打乱了之前的成果”，导致大量重复工作。所以好的步长序列希望相邻步长之间分组结构重叠尽量少，让每轮都能在新的维度上修正位置。
考虑到绝大多数实际应用里数据量不会大到必须追求理论最优步长，我的建议很直接：数据量几千到几万，用折半递减足够；如果对性能有更高要求，可以换 2^k - 1 序列做一次对比测量，哪个快用哪个。不必为了理论最优步长在工程里搞复杂推导，收益往往没那么明显。
3. 希尔排序 Python 实现：从最简单版本到可复用封装
3.1 最简单的“教科书版”实现
先看最直白的版本，核心逻辑全部摊开，方便你理解每一行在干什么。
def shell_sort_simple(arr): n = len(arr) gap = n // 2 while gap > 0: for i in range(gap, n): temp = arr[i] j = i while j >= gap and arr[j - gap] > temp: arr[j] = arr[j - gap] j -= gap arr[j] = temp gap //= 2 return arr这段代码只有几层循环，但每一层都有明确职责。
外层while gap > 0控制步长从 n//2 一直递减到 1。for i in range(gap, n)遍历当前步长下每一组的所有元素，i可以理解成“当前要插入的元素在原始数组中的真实下标”。内层while做的事情是：把arr[i]拿出来，跟它前面距离 gap 的元素比较，如果前一个更大，就把前一个往后挪一个 gap 的位置，然后继续向前跳 gap。
整个过程和普通插入排序几乎一样，唯一的差别是把“相邻距离 1”换成了“相邻距离 gap”。为了不丢失当前要插入的值，需要先把temp = arr[i]保存起来，因为循环里会把它的位置覆盖掉。
我用一个简单场景验证一下：
arr = [64, 34, 25, 12, 22, 11, 90] print(shell_sort_simple(arr))输出[11, 12, 22, 25, 34, 64, 90]，结果正确。你也可以在自己环境里跑跑看。
3.2 支持自定义增量序列的进阶版本
工程实践里，你可能想用不同的步长方案做对比。这时候把 gap 序列抽象成参数更合适。
def shell_sort(arr, gap_sequence=None): n = len(arr) if gap_sequence is None: gaps = [] gap = n // 2 while gap > 0: gaps.append(gap) gap //= 2 else: gaps = gap_sequence for gap in gaps: for i in range(gap, n): temp = arr[i] j = i while j >= gap and arr[j - gap] > temp: arr[j] = arr[j - gap] j -= gap arr[j] = temp return arr调用方式可以是这样：
# 使用折半递减 data = [9, 8, 7, 6, 5, 4, 3, 2, 1] shell_sort(data) # 自定义步长序列，注意要从大到小排列，并且一定要以 1 结尾 data2 = [9, 8, 7, 6, 5, 4, 3, 2, 1] shell_sort(data2, gap_sequence=[4, 2, 1])这个封装让“换步长策略”变成只改一个参数的事。我会在下一节专门说增量序列对性能的影响，这里先记住一个原则：传入的 gap 序列最好是从大到小，并且必须以 1 结束。如果传入的序列里没有 1，那最后一次排序还是按照大于 1 的间隔分组，最后不会把数组完全排有序。
3.3 边界情况与防御性写法
写排序算法，不能只在正常数组上测试，空数组、单元素数组、重复元素数组、浮点数、负数这些都该验证一遍。下面是一种更稳健的写法：
def shell_sort_safe(arr): n = len(arr) if n <= 1: return arr gap = n // 2 while gap > 0: for i in range(gap, n): temp = arr[i] j = i while j >= gap and arr[j - gap] > temp: arr[j] = arr[j - gap] j -= gap arr[j] = temp gap //= 2 return arr这里最关键的就是一开始if n <= 1: return arr。理由很朴素：数组为空或只有一个元素时，根本不需要排序，直接返回就行。如果不加判断，n=0 时gap = 0，不会进入外层循环，倒也能正常返回；但加上这个判断，代码意图更清晰，后续逻辑也不用担心出现奇怪的边界下标。
对于重复元素，希尔排序的比较条件用了严格大于>，所以相同的元素不会被交换位置，不会破坏重复值之间的相对顺序。使用>=则会让相等元素在分组阶段被交换，稳定性就彻底没了，这一点下一节细说。
实际处理字符串列表时，同样的代码也能排序字符串，因为字符串本身支持大小比较，比如"apple" < "banana"。不过如果列表里混合了数字和字符串，比较大小会抛出TypeError，这是 Python 的类型机制决定的，不算是希尔排序的缺陷。
4. 复杂度分析与边界情况：别被“O(n²)”迷惑
4.1 为什么希尔排序的时间复杂度特别难算
你翻很多教材，会发现希尔排序的时间复杂度写得五花八门。有人写 O(n²)，有人写 O(n^(3/2))，还有人直接写“依赖于增量序列”。造成这种混乱的原因很实际：希尔排序的耗时不仅取决于数组长度，还取决于步长序列和数据分布。
步长不同，分组方式就不同，每一组子序列的规模、元素间相对位置都不同。例如折半递减在有些特殊数据上，前一组的排序成果会被后一组部分破坏，增加了总比较次数，最坏情况能达到 O(n²)。而某些精心设计的步长序列，可以保证子序列之间重叠更少，复杂度能压到 O(n^(3/2)) 甚至更好。
空间复杂度倒是很明确：O(1)。整个排序过程在原数组上完成，没有额外创建和数组等长的辅助空间。这一点比归并排序更省内存。
说了这么多，我想给你一个工程判断：希尔排序的“理论复杂度”不是它最大的卖点。它最大的优势是代码短、思路简单、原地排序、对中等规模数据实测加速明显。如果你要写一个不依赖高级技巧、又要比普通插入排序强不少的算法，希尔排序是性价比很高的选择。
4.2 希尔排序是不稳定的排序算法
稳定性是排序算法的一个重要属性，意思是：如果两个元素的值相等，排序后它们的相对顺序保持不变。插入排序是稳定的，希尔排序却不一定。
为什么？看这个例子。对下面的二维结构按第一列数字排序：
[(3, 'a'), (2, 'b'), (3, 'c')]如果直接做普通插入排序，两个 3 不会交换位置，排完是[(2, 'b'), (3, 'a'), (3, 'c')]。但希尔排序在 gap > 1 时，会把(3, 'a')和(3, 'c')分到不同组或者不同位置，分组插入的过程可能让它们越过彼此。最后排完可能变成[(2, 'b'), (3, 'c'), (3, 'a')]，两个 3 的相对顺序颠倒了。
如果你的业务场景要求相等元素保持原始顺序，希尔排序就不合适，应该用稳定排序如归并排序或普通插入排序。不过对纯数值排序，稳定性一般不重要，可以忽略这个约束。
4.3 实测对比：插入排序、希尔排序、快速排序
理论说再多，不如跑一次数据。我给三份代码大致相同的测试脚本，用随机数组看时间差距：
import random import time def insertion_sort(arr): for i in range(1, len(arr)): temp = arr[i] j = i - 1 while j >= 0 and arr[j] > temp: arr[j + 1] = arr[j] j -= 1 arr[j + 1] = temp return arr def shell_sort(arr): n = len(arr) gap = n // 2 while gap > 0: for i in range(gap, n): temp = arr[i] j = i while j >= gap and arr[j - gap] > temp: arr[j] = arr[j - gap] j -= gap arr[j] = temp gap //= 2 return arr def quick_sort(arr): if len(arr) <= 1: return arr pivot = arr[len(arr) // 2] left = [x for x in arr if x < pivot] middle = [x for x in arr if x == pivot] right = [x for x in arr if x > pivot] return quick_sort(left) + middle + quick_sort(right) n = 10000 data = list(range(n)) random.shuffle(data) data1 = data.copy() t0 = time.time() insertion_sort(data1) t1 = time.time() data2 = data.copy() t0 = time.time() shell_sort(data2) t1 = time.time() data3 = data.copy() t0 = time.time() quick_sort(data3) t1 = time.time()我实测过一组大小约 10000 的乱序整数数组，插入排序耗时在 1 秒多，希尔排序大概 20 到 40 毫秒，快速排序大概 10 毫秒以内。希尔排序比插入排序快了几十倍，已经能明显感知到差距，但和快速排序这类 O(n log n) 算法相比仍有距离。
如果数据本身接近有序，情况会有所变化。插入排序在这种场景可能跑出接近 O(n) 的效果，希尔排序也不会差，但不会比插入排序快出一个数量级。你可以根据自己的数据特性决定用哪个。
4.4 什么场景适合用希尔排序，什么场景不适合
适合使用的场景主要有三类。第一是嵌入式或内存敏感环境，因为希尔排序只占用常数额外空间，代码短，没有递归调用栈。第二是数据量在中等规模、且希望原地排序，比如几千到几万条记录。第三是教学或面试中想展示一种比基础插入排序更高效的思路。
不适合的场景也很明确。数据量上百万时，O(n log n) 级别的算法优势会非常明显，希尔排序通常不是首选。如果要求稳定排序，也不能用。如果代码库里已经有封装好的高性能排序函数，直接用现成的往往更快，因为底层很可能是高度优化的混合排序。
5. 实际调试经验与几个容易踩的坑
5.1 内层循环方向写反会导致什么结果
我见过不少初学者会把内层循环写成从左边往右边“推”。比如：
while j < n - gap and arr[j] > arr[j + gap]: arr[j], arr[j + gap] = arr[j + gap], arr[j] j += gap这种写法其实做的不是插入排序，而是一种“冒泡式搬运”。它能在一个子序列内交换元素，但每次只把较大值往后挪一格，然后再从新位置继续往后比。效果上有点接近插入排序的逆向操作，但整体效率和正确逻辑都不对，结果数组可能只保证每组内部“大致有序”，并不能保证最后完全有序。
正确做法一定是先把当前元素存到temp，然后不断向左比较、把较大元素往右覆盖，最后把temp放到空位。这个“搬动-覆盖-插入”的过程，和普通插入排序一模一样，只是把步长从 1 换成了 gap。
调试小技巧：如果你怀疑方向有问题，在每次外层 gap 结束后打印数组，观察是否每个分组内都已经有序。如果有一组没排好，问题一定出在内层循环的边界或比较方向上。
5.2 gap 更新位置不对造成死循环或漏排
另一个很常见的坑是 gap 更新的位置或者步长错了。比如把gap //= 2写在了内层 for 循环里，那么每处理一个元素 gap 就变小一次，完全破坏了分组逻辑，排序结果不稳定。
还有人会把 gap 初始值写成n而不是n // 2。如果 gap 等于 n，那么for i in range(gap, n)根本没有元素可处理，内层循环空转，然后 gap 缩小成 n//2 才开始正式工作。虽然最终结果一般还是对的，但白走了一轮循环，没必要。
最稳妥的检查方式是打印每次 gap 进入前的状态：
while gap > 0: print(f"gap = {gap}") for i in range(gap, n): # ... gap //= 2一个正确希尔排序的 gap 序列应该严格递减，且最后一次一定是 1。如果你打印出来发现某次 gap 跳过了 1，那多半是缩小时的整除逻辑写错了。
5.3 不要为了“直观”去反复切片复制数组
有些同学为了展示分组过程，会写这样的代码：
for start in range(gap): group = arr[start::gap] group.sort() arr[start::gap] = group这段代码虽然逻辑正确，排序结果也对，但有明显问题：每次分组都会生成新的切片列表，还调用了 Python 自带的sort，内存和时间的开销都变大了，而且在原地算法里显得很怪。切片赋值本质上还是复制回原数组，复杂度并不低。
如果你只是学习演示，这样写可以理解，但如果你想让希尔排序体现“原地、轻量”的优势，最好还是用原生三循环版本。我实际使用中基本不用切片分组方式，因为它把希尔排序的空间优势全丢了。
5.4 用“打印数组变化”理解分组，而不是凭想象
学习希尔排序最容易困惑的地方是“分组到底在内存里怎么排”。很多人以为希尔排序会把数组重新排列成多组再分别排序，其实并没有。数组从头到尾只维持一个序列，我们只是通过下标模 gap 的规则，逻辑上把它看成若干组，并在同一份数组上完成所有组的插入排序。
前期调试时，我建议在每次 gap 循环结束后打印数组，并人工画一下分组。比如：
data = [9, 8, 7, 6, 5, 4, 3, 2, 1] gap = 4打印后你能看到第一组元素是下标 0, 4, 8，排完后数组里这些位置已经有序。看多了这种过程，你会真正理解希尔排序的“跨越式移动”是怎么发生的。
5.5 我自己用希尔排序的一点习惯
我现在写排序代码，遇到中等规模、内存紧张、不允许引入复杂依赖的场景，会优先考虑希尔排序。折半递减最省心，代码短不容易写错。如果换成 2^k - 1 步长序列，我会先在同一份数据上做性能对比，确认收益明显再改用，不会凭感觉觉得“理论更优就一定更快”。
另外我会把希尔排序函数设计成接收 gap 序列参数的形式，便于后续调优和测试。排序之前也习惯先打印一次原始数组的前几十个元素，排序后再对比一次，这在定位错误时比单纯看最终结果有效得多。
排序算法没有银弹，希尔排序也不是万能钥匙。但作为一个原理好懂、实现简单、性能提升可观的中间选项，它值得放进你的工具集里。遇到合适场景拿起来就用，比临时翻资料强太多。
