希尔排序 (Shell Sort)分组插入的增量缩减摘要插入排序在小数据和近乎有序场景下表现出色但面对完全逆序数据时退化为 O(n²)——每个元素都要移动到底。希尔排序的核心洞察是先做大跨度的粗排再做小跨度的细排。通过递减增量将数组分组做插入排序大增量阶段快速消除大量逆序对使最后一轮 gap1 的插入排序面对的是近乎有序的数据接近 O(n)。本文从插入排序的最坏情况出发图解希尔排序的分组与增量缩减过程给出基于 Knuth 增量序列的 Python 完整实现对比不同增量序列的性能差异并分析其在工业实践中的定位。本文属于专栏《算法》系列 1 第 8 篇 | 上一篇选择排序 (Selection Sort)| 下一篇1-9-梳排序-CombSort文章目录希尔排序 (Shell Sort)分组插入的增量缩减一、问题引入二、算法原理图解核心思想图解分组过程关键观察增量序列的选择与插入排序的对比三、代码实现完整实现增量序列辅助函数运行验证四、复杂度分析时间复杂度空间复杂度稳定性五、横向对比希尔排序 vs 插入排序何时更快六、工程实战希尔排序的实际定位嵌入式与资源受限环境Linux 内核中的希尔排序为什么标准库不用希尔排序七、常见误区与面试题高频面试题常见实现错误八、总结一、问题引入上一篇文章中插入排序在近乎有序数据上接近 O(n)但在完全逆序数据上退化为 O(n²)。问题出在哪里考虑完全逆序数组[5, 4, 3, 2, 1]升序排序元素1在位置 4需要移动到位置 0——跨 4 个位置插入排序每次只能移动 1 步j - 1所以1需要 4 次后移元素2需要移动 3 步3需要 2 步4需要 1 步总移动次数 4 3 2 1 10 O(n²)根本原因插入排序的步长始终为 1元素只能一步一步挪动无法快速跨越长距离。能否让元素一次跳多步希尔排序的回答用递减的增量分组先大跨度消除逆序对再小跨度精细调整。考虑数组[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]升序排序插入排序元素0从位置 9 移到位置 0需要 9 步希尔排序 gap40与4同组位置 4, 8先交换到位置 4 附近gap1 时再从位置 4 移到位置 0只需 4 步希尔排序的核心思想先粗排后细排让大跨度消除逆序对小跨度精细微调。问题定义输入含 n 个元素的可比较数组arr输出按升序或降序排列的数组核心操作选择增量 → 分组插入排序 → 缩减增量 → 重复直至 gap1二、算法原理图解核心思想希尔排序是对插入排序的改进关键在于跨步长插入排序选择增量序列如 Knuth 序列1, 4, 13, 40, ...递推h 3h 1从最大增量开始按步长gap将数组分为gap组每组做插入排序缩减增量gap // 3继续分组插入排序最终 gap1此时数组已基本有序一次普通插入排序即可完成图解分组过程以[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]升序排序为例n10原数组: 9 8 7 6 5 4 3 2 1 0 索引: 0 1 2 3 4 5 6 7 8 9 Knuth 增量序列n10: [4, 1] --- gap4 分组插入排序 --- 组0: 索引 0,4,8 → [9, 5, 1] → 排序 → [1, 5, 9] 组1: 索引 1,5,9 → [8, 4, 0] → 排序 → [0, 4, 8] 组2: 索引 2,6 → [7, 3] → 排序 → [3, 7] 组3: 索引 3,7 → [6, 2] → 排序 → [2, 6] gap4 后: 1 0 3 2 5 4 7 6 9 8 --- gap1 全数组插入排序 --- 此时数组已基本有序每元素离正确位置最多差 1-2 位 插入排序接近 O(n) 完成 最终结果: 0 1 2 3 4 5 6 7 8 9关键观察大增量消除长距离逆序对gap4 时元素0从位置 9 跳到位置 1一步跨 8 位小增量精细调整gap1 时只需微调因为大增量已经让每个元素离正确位置不远逆序对逐步递减每轮增量缩减后逆序对数量都比上一轮少增量序列的选择增量序列直接决定希尔排序的时间复杂度增量序列递推公式最坏复杂度说明Shell 原始n/2, n/4, …, 1O(n²)最简单但存在最坏退化Knuth 序列1, 4, 13, 40, …O(n^1.5)实践中最常用Sedgewick1, 5, 19, 41, 109, …O(n^(4/3))理论更优但实现复杂Pratt2^i × 3^jO(n log²n)理论最优但组数过多本文采用Knuth 增量序列递推公式h 3h 1生成1, 4, 13, 40, 121, ...最坏情况约 O(n^1.5)实践中平均约 O(n^1.3)。与插入排序的对比维度插入排序希尔排序步长固定为 1递减gap → 1跨距离移动不支持一步一挪支持跨 gap 跳跃完全逆序数据O(n²)约 O(n^1.3~1.5)近乎有序数据O(n)接近 O(n)gap1 阶段稳定性稳定不稳定跨组交换空间O(1)O(1)核心改进希尔排序本质上是多次不同步长的插入排序大步长消除长距离逆序对小步长精细微调。最后一轮 gap1 时数组已基本有序普通插入排序接近 O(n)。三、代码实现完整代码通过网盘分享的文件算法链接: https://pan.baidu.com/s/1DTJt1X2Is_IQeH5fAXvtZg?pwdyyqf 提取码: yyqf–来自百度网盘超级会员v4的分享完整实现defshell_sort(arr,ascendingTrue): 希尔排序按递减增量对数组进行分组插入排序最后增量为1时完成全排序。 核心改进插入排序对近乎有序数据极快希尔排序先通过大增量分组 消除大量逆序对使最后一轮 gap1 的插入排序接近 O(n)。 时间复杂度取决于增量序列平均约 O(n^1.3) | 空间复杂度O(1) | 不稳定排序 参数: arr: 待排序列表 ascending: 排序方向True升序默认False降序 返回: 排序后的列表原地排序 nlen(arr)ifn1:returnarr# Knuth 增量序列1, 4, 13, 40, 121, ...递推 h 3h 1gap1whilegapn//3:gap3*gap1# 增量从大到小递减每组做插入排序whilegap1:# 对每个 gap 组执行插入排序跨步长 gap 的插入排序foriinrange(gap,n):currentarr[i]ji-gap# 升序前驱大于 current 则后移降序前驱小于 current 则后移ifascending:whilej0andarr[j]current:arr[jgap]arr[j]j-gapelse:whilej0andarr[j]current:arr[jgap]arr[j]j-gap arr[jgap]current gap//3# 缩减增量returnarr三个关键设计Knuth 增量序列h 3h 1生成1, 4, 13, 40, ...最坏约 O(n^1.5)优于 Shell 原始序列的 O(n²)跨步长插入排序内层while的步长为gap而非 1元素可以跨gap个位置跳跃快速消除长距离逆序对增量递减至 1最后一轮 gap1 是普通插入排序但此时数组已基本有序接近 O(n)增量序列辅助函数def_get_gap_sequence(n):生成 Knuth 增量序列用于调试观察。gaps[]gap1whilegapn:gaps.append(gap)gap3*gap1returngaps[::-1]# 从大到小运行验证if__name____main__:data[64,34,25,12,22,11,90]print(f排序前:{data})print(f升序:{shell_sort(data[:])})print(f降序:{shell_sort(data[:],ascendingFalse)})# 边界测试print(f空列表:{shell_sort([])})print(f单元素:{shell_sort([42])})print(f已有序:{shell_sort([1,2,3,4,5])})print(f全相同:{shell_sort([7,7,7,7,7])})print(f逆序:{shell_sort([5,4,3,2,1])})输出排序前: [64, 34, 25, 12, 22, 11, 90] 升序: [11, 12, 22, 25, 34, 64, 90] 降序: [90, 64, 34, 25, 22, 12, 11] 空列表: [] 单元素: [42] 已有序: [1, 2, 3, 4, 5] 全相同: [7, 7, 7, 7, 7] 逆序: [1, 2, 3, 4, 5]完全逆序 5000 个元素下希尔排序比插入排序快近 200 倍——这就是增量缩减的核心价值。四、复杂度分析时间复杂度情况复杂度说明最好O(n log n)已有序数据每轮 gap 只比较不后移平均约 O(n^1.3)取决于增量序列Knuth 序列下经验值最坏O(n^1.5)Knuth 序列最坏情况Shell 原始序列最坏 O(n²)推导过程为何希尔排序比插入排序快插入排序步长1的逆序对消除效率 每次后移只能消除 1 个相邻逆序对 完全逆序数组有 n(n-1)/2 个逆序对 → O(n²) 希尔排序步长gap的逆序对消除效率 gap13 时每次后移消除 1 个跨距 13 的逆序对 这等价于消除了至多 13 个相邻逆序对 大增量阶段快速消除大量逆序对 → 剩余逆序对极少 当 gap1 时 数组已基本有序逆序对被大增量阶段大量消除 插入排序接近 O(n)核心结论希尔排序的时间复杂度严格依赖于增量序列的选择没有简单的精确公式。Knuth 序列下平均约 O(n^1.3)这是理论分析和实验统计的经验值。空间复杂度O(1)——仅使用current、i、j、gap等常数个辅助变量原地排序。稳定性不稳定排序。相同元素可能被分到不同组跨组交换后相对顺序可能改变。例如[3a, 2, 3b, 1]gap2 时组0[3a, 3b]→ 不变组1[2, 1]→ 交换为[1, 2]结果[3a, 1, 3b, 2]gap1 排序后[1, 2, 3a, 3b]或[1, 2, 3b, 3a]五、横向对比希尔排序与同系列算法的对比算法平均时间最好时间最坏时间空间稳定性特点冒泡排序O(n²)O(n)O(n²)O(1)稳定最简单插入排序O(n²)O(n)O(n²)O(1)稳定小数据最优选择排序O(n²)O(n²)O(n²)O(1)不稳定交换最少希尔排序O(n^1.3)O(n log n)O(n^1.5)O(1)不稳定原地 亚平方快速排序O(n log n)O(n log n)O(n²)O(log n)不稳定通用最快归并排序O(n log n)O(n log n)O(n log n)O(n)稳定稳定不退化希尔排序 vs 插入排序何时更快数据特征插入排序希尔排序胜出已有序n5000O(n)O(n log n)插入近乎有序接近 O(n)接近 O(n)持平完全逆序n50000.9848s0.0050s希尔197倍随机数据n50000.5042s0.0091s希尔55倍选型建议数据量极小n 20插入排序常数因子更小无需增量初始化开销数据量中等20 n 1000希尔排序O(n^1.3) 优于 O(n²)且原地排序数据量大n 1000快速排序或 TimSortO(n log n) 渐近更优内存受限 中等数据量希尔排序O(1) 空间 亚平方复杂度六、工程实战希尔排序的实际定位希尔排序是O(n²) 到 O(n log n) 之间的过渡算法维度O(n²) 系列希尔排序O(n log n) 系列代表冒泡/插入/选择希尔排序快排/归并/堆排复杂度O(n²)O(n^1.3~1.5)O(n log n)空间O(1)O(1)O(1)~O(n)稳定性可选不稳定可选适用场景小数据中等数据大数据嵌入式与资源受限环境在嵌入式系统中希尔排序有其独特价值O(1) 空间不像归并排序需要 O(n) 额外空间无递归不像快速排序需要递归栈O(log n)希尔排序是纯迭代代码量小核心逻辑仅一个循环嵌套适合固件开发Linux 内核中的希尔排序Linux 内核的lib/sort.c中提供了希尔排序的实现用于内核中中小规模数组排序。选择希尔排序而非快排的原因内核栈空间有限递归有溢出风险希尔排序是纯迭代安全可控内核排序数据量通常不大O(n^1.3) 足够为什么标准库不用希尔排序原因说明复杂度不够优O(n^1.3) 比 O(n log n) 差一个数量级不稳定标准库通常需要稳定排序保证语义正确增量序列敏感不同增量序列性能差异大缺乏普适最优解TimSort 更优部分有序数据下 TimSort 接近 O(n)且稳定七、常见误区与面试题高频面试题Q1希尔排序比插入排序快在哪里插入排序的步长始终为 1元素只能一步一步挪动消除一个相邻逆序对需要一次后移。希尔排序用递减增量分组大增量阶段每次后移可以跨越gap个位置等价于一次性消除至多gap个相邻逆序对。经过几轮大增量排序后数组中剩余的逆序对极少最后一轮 gap1 的插入排序接近 O(n)。Q2希尔排序的时间复杂度是多少希尔排序的时间复杂度严格依赖于增量序列的选择没有简单的精确公式Shell 原始序列n/2, n/4, …最坏 O(n²)Knuth 序列1, 4, 13, …最坏 O(n^1.5)平均约 O(n^1.3)Sedgewick 序列最坏 O(n^(4/3))实践中通常说约 O(n^1.3)这是 Knuth 序列下的经验值。Q3希尔排序是稳定的吗为什么不稳定。相同元素可能被分到不同组跨组做插入排序后相对顺序可能改变。例如[3a, 2, 3b, 1]gap2 时 3a 和 3b 分在同一组不变但 2 和 1 分在同一组交换最终结果中 3a 和 3b 的相对顺序可能被 gap1 阶段改变。Q4为什么希尔排序的最后一轮 gap1 很重要gap1 是普通插入排序它有两重意义保证正确性只有 gap1 才能确保所有相邻元素都经过比较最终数组完全有序效率极高经过大增量阶段后数组已基本有序每个元素离正确位置不远插入排序在近乎有序数据上接近 O(n)如果去掉 gap1 这一步前面的大增量排序只能保证组内有序不能保证全局有序。常见实现错误错误说明修正忘记最后一轮 gap1数组组内有序但全局无序while gap 1确保 gap1 必须执行步长写成 1 而非 gap退化为普通插入排序j - gap而非j - 1增量序列选错用 n/2 序列可能退化 O(n²)使用 Knuth 序列h 3h 1增量初始化错误gap 从 n 开始而非最大 Knuth 值while gap n // 3: gap 3 * gap 1内层循环范围错误从 0 开始而非 gap 开始for i in range(gap, n)前 gap 个元素是各组第一个八、总结希尔排序的核心要点分组插入 增量缩减——先用大步长跨距离消除逆序对再用小步长精细微调Knuth 增量序列——h 3h 1生成1, 4, 13, 40, ...最坏 O(n^1.5)平均约 O(n^1.3)最后一轮 gap1 是关键——前面的粗排使最后一轮插入排序面对近乎有序数据接近 O(n)原地 不稳定——O(1) 空间但跨组交换破坏稳定性O(n²) 到 O(n log n) 的过渡——中等数据量n100~5000下的实用选择嵌入式和内核场景仍有价值希尔排序是排序算法演进史上的重要里程碑——它首次打破了步长必须为 1的思维定式证明了通过调整步长可以将 O(n²) 降至亚平方。理解了先粗排后细排的增量缩减思想后续的梳排序递减间隔改进冒泡、块排序归并的块化变体都能在此基础上自然延伸。专栏导航算法⬅️上一篇选择排序 (Selection Sort) ➡️下一篇1-9-梳排序-CombSort如果这篇文章对你有帮助欢迎点赞、收藏、关注支持专栏持续更新