1-8-希尔排序-ShellSort

希尔排序 (Shell Sort)：分组插入的增量缩减

摘要：插入排序在小数据和近乎有序场景下表现出色，但面对完全逆序数据时退化为 O(n²)——每个元素都要移动到底。希尔排序的核心洞察是：先做大跨度的粗排，再做小跨度的细排。通过递减增量将数组分组做插入排序，大增量阶段快速消除大量逆序对，使最后一轮 gap=1 的插入排序面对的是近乎有序的数据，接近 O(n)。本文从插入排序的最坏情况出发，图解希尔排序的分组与增量缩减过程，给出基于 Knuth 增量序列的 Python 完整实现，对比不同增量序列的性能差异，并分析其在工业实践中的定位。

本文属于专栏《算法》系列 1 第 8 篇 | 上一篇：选择排序 (Selection Sort)| 下一篇：1-9-梳排序-CombSort

一、问题引入

上一篇文章中，插入排序在近乎有序数据上接近 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 步
• 希尔排序 gap=4：0与4同组（位置 4, 8），先交换到位置 4 附近；gap=1 时再从位置 4 移到位置 0，只需 4 步

希尔排序的核心思想：先粗排后细排，让大跨度消除逆序对，小跨度精细微调。

问题定义：

• 输入：含 n 个元素的可比较数组arr
• 输出：按升序（或降序）排列的数组
• 核心操作：选择增量 → 分组插入排序 → 缩减增量 → 重复直至 gap=1

二、算法原理图解

核心思想

希尔排序是对插入排序的改进，关键在于跨步长插入排序：

1. 选择增量序列：如 Knuth 序列1, 4, 13, 40, ...（递推h = 3h + 1）
2. 从最大增量开始：按步长gap将数组分为gap组，每组做插入排序
3. 缩减增量：gap //= 3，继续分组插入排序
4. 最终 gap=1：此时数组已基本有序，一次普通插入排序即可完成

图解分组过程

以[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]升序排序为例，n=10：

原数组: 9 8 7 6 5 4 3 2 1 0 索引: 0 1 2 3 4 5 6 7 8 9 Knuth 增量序列（n=10）: [4, 1] --- gap=4 分组插入排序 --- 组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] gap=4 后: 1 0 3 2 5 4 7 6 9 8 --- gap=1 全数组插入排序 --- 此时数组已基本有序（每元素离正确位置最多差 1-2 位） 插入排序接近 O(n) 完成 最终结果: 0 1 2 3 4 5 6 7 8 9

关键观察

1. 大增量消除长距离逆序对：gap=4 时，元素0从位置 9 跳到位置 1，一步跨 8 位
2. 小增量精细调整：gap=1 时只需微调，因为大增量已经让每个元素离正确位置不远
3. 逆序对逐步递减：每轮增量缩减后，逆序对数量都比上一轮少

增量序列的选择

增量序列直接决定希尔排序的时间复杂度：

本文采用Knuth 增量序列：递推公式h = 3h + 1，生成1, 4, 13, 40, 121, ...，最坏情况约 O(n^1.5)，实践中平均约 O(n^1.3)。

与插入排序的对比

核心改进：希尔排序本质上是"多次不同步长的插入排序"，大步长消除长距离逆序对，小步长精细微调。最后一轮 gap=1 时数组已基本有序，普通插入排序接近 O(n)。

三、代码实现

完整代码

通过网盘分享的文件：算法
链接: https://pan.baidu.com/s/1DTJt1X2Is_IQeH5fAXvtZg?pwd=yyqf 提取码: yyqf
–来自百度网盘超级会员v4的分享

完整实现

defshell_sort(arr,ascending=True):""" 希尔排序：按递减增量对数组进行分组插入排序，最后增量为1时完成全排序。 核心改进：插入排序对近乎有序数据极快，希尔排序先通过大增量分组 消除大量逆序对，使最后一轮 gap=1 的插入排序接近 O(n)。 时间复杂度：取决于增量序列，平均约 O(n^1.3) | 空间复杂度：O(1) | 不稳定排序 参数: arr: 待排序列表 ascending: 排序方向，True=升序（默认），False=降序 返回: 排序后的列表（原地排序） """n=len(arr)ifn<=1:returnarr# Knuth 增量序列：1, 4, 13, 40, 121, ...（递推 h = 3h + 1）gap=1whilegap<n//3:gap=3*gap+1# 增量从大到小递减，每组做插入排序whilegap>=1:# 对每个 gap 组执行插入排序（跨步长 gap 的插入排序）foriinrange(gap,n):current=arr[i]j=i-gap# 升序：前驱大于 current 则后移；降序：前驱小于 current 则后移ifascending:whilej>=0andarr[j]>current:arr[j+gap]=arr[j]j-=gapelse:whilej>=0andarr[j]<current:arr[j+gap]=arr[j]j-=gap arr[j+gap]=current gap//=3# 缩减增量returnarr

三个关键设计：

• Knuth 增量序列：h = 3h + 1生成1, 4, 13, 40, ...，最坏约 O(n^1.5)，优于 Shell 原始序列的 O(n²)
• 跨步长插入排序：内层while的步长为gap而非 1，元素可以跨gap个位置跳跃，快速消除长距离逆序对
• 增量递减至 1：最后一轮 gap=1 是普通插入排序，但此时数组已基本有序，接近 O(n)

增量序列辅助函数

def_get_gap_sequence(n):"""生成 Knuth 增量序列，用于调试观察。"""gaps=[]gap=1whilegap<n:gaps.append(gap)gap=3*gap+1returngaps[::-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[:],ascending=False)}")# 边界测试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 倍——这就是增量缩减的核心价值。

四、复杂度分析

时间复杂度

推导过程（为何希尔排序比插入排序快）：

插入排序（步长=1）的逆序对消除效率： 每次后移只能消除 1 个相邻逆序对 完全逆序数组有 n(n-1)/2 个逆序对 → O(n²) 希尔排序（步长=gap）的逆序对消除效率： gap=13 时，每次后移消除 1 个跨距 13 的逆序对 这等价于消除了至多 13 个相邻逆序对 大增量阶段快速消除大量逆序对 → 剩余逆序对极少 当 gap=1 时： 数组已基本有序（逆序对被大增量阶段大量消除） 插入排序接近 O(n)

核心结论：希尔排序的时间复杂度严格依赖于增量序列的选择，没有简单的精确公式。Knuth 序列下平均约 O(n^1.3)，这是理论分析和实验统计的经验值。

空间复杂度

O(1)——仅使用current、i、j、gap等常数个辅助变量，原地排序。

稳定性

不稳定排序。相同元素可能被分到不同组，跨组交换后相对顺序可能改变。

例如[3a, 2, 3b, 1]，gap=2 时：

• 组0：[3a, 3b]→ 不变
• 组1：[2, 1]→ 交换为[1, 2]
• 结果[3a, 1, 3b, 2]，gap=1 排序后[1, 2, 3a, 3b]或[1, 2, 3b, 3a]

五、横向对比

希尔排序与同系列算法的对比：

希尔排序 vs 插入排序：何时更快？

选型建议：

• 数据量极小（n < 20）：插入排序（常数因子更小，无需增量初始化开销）
• 数据量中等（20 < n < 1000）：希尔排序（O(n^1.3) 优于 O(n²)，且原地排序）
• 数据量大（n > 1000）：快速排序或 TimSort（O(n log n) 渐近更优）
• 内存受限 + 中等数据量：希尔排序（O(1) 空间 + 亚平方复杂度）

六、工程实战

希尔排序的实际定位

希尔排序是O(n²) 到 O(n log n) 之间的过渡算法：

嵌入式与资源受限环境

在嵌入式系统中，希尔排序有其独特价值：

1. O(1) 空间：不像归并排序需要 O(n) 额外空间
2. 无递归：不像快速排序需要递归栈（O(log n)），希尔排序是纯迭代
3. 代码量小：核心逻辑仅一个循环嵌套，适合固件开发

Linux 内核中的希尔排序

Linux 内核的lib/sort.c中提供了希尔排序的实现，用于内核中中小规模数组排序。选择希尔排序而非快排的原因：

• 内核栈空间有限，递归有溢出风险
• 希尔排序是纯迭代，安全可控
• 内核排序数据量通常不大，O(n^1.3) 足够

为什么标准库不用希尔排序？

七、常见误区与面试题

高频面试题

Q1：希尔排序比插入排序快在哪里？

插入排序的步长始终为 1，元素只能一步一步挪动，消除一个相邻逆序对需要一次后移。希尔排序用递减增量分组，大增量阶段每次后移可以跨越gap个位置，等价于一次性消除至多gap个相邻逆序对。经过几轮大增量排序后，数组中剩余的逆序对极少，最后一轮 gap=1 的插入排序接近 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]，gap=2 时 3a 和 3b 分在同一组（不变），但 2 和 1 分在同一组（交换），最终结果中 3a 和 3b 的相对顺序可能被 gap=1 阶段改变。

Q4：为什么希尔排序的最后一轮 gap=1 很重要？

gap=1 是普通插入排序，它有两重意义：

1. 保证正确性：只有 gap=1 才能确保所有相邻元素都经过比较，最终数组完全有序
2. 效率极高：经过大增量阶段后，数组已基本有序（每个元素离正确位置不远），插入排序在近乎有序数据上接近 O(n)

如果去掉 gap=1 这一步，前面的大增量排序只能保证"组内有序"，不能保证"全局有序"。

常见实现错误

八、总结

希尔排序的核心要点：

1. 分组插入 + 增量缩减——先用大步长跨距离消除逆序对，再用小步长精细微调
2. Knuth 增量序列——h = 3h + 1生成1, 4, 13, 40, ...，最坏 O(n^1.5)，平均约 O(n^1.3)
3. 最后一轮 gap=1 是关键——前面的粗排使最后一轮插入排序面对近乎有序数据，接近 O(n)
4. 原地 + 不稳定——O(1) 空间，但跨组交换破坏稳定性
5. O(n²) 到 O(n log n) 的过渡——中等数据量（n=100~5000）下的实用选择，嵌入式和内核场景仍有价值

希尔排序是排序算法演进史上的重要里程碑——它首次打破了"步长必须为 1"的思维定式，证明了通过调整步长可以将 O(n²) 降至亚平方。理解了"先粗排后细排"的增量缩减思想，后续的梳排序（递减间隔改进冒泡）、块排序（归并的块化变体）都能在此基础上自然延伸。

📌专栏导航：算法

⬅️上一篇：选择排序 (Selection Sort) ➡️下一篇：1-9-梳排序-CombSort

如果这篇文章对你有帮助，欢迎点赞、收藏、关注，支持专栏持续更新！