01先把问题说具体
逆序数组中的小元素要向左移动很多次。能否先让它跨较远距离,再做精细调整?
02一步步得到方法
一个 gap 对应多条交错子序列
gap=3 时,下标 0,3,6,… 是一条子序列,1,4,7,… 是另一条。对每条子序列做插入排序后,数组是 gap-有序,而不是整体有序。不同子序列之间仍可能逆序。
随后缩小 gap,重复间隔插入。最后必须取 gap=1,此时就是普通插入排序,因此保证最终有序。前面的大步调整让小元素较快到达左侧,可能减少最后阶段的移动。
沿用插入排序的 key 思想
先保存 key=a[i],将同一子序列里比 key 大的元素每次右移 gap 个位置,直到找到插入点。判断 j>=gap 防止访问负下标;不能直接照搬 j>0。
本课使用 n//2 不断减半的简单增量。不同增量序列有不同理论界,不能把希尔排序统一写成 O(n log n)。本序列最坏时间可达 O(n²),实际效果需按输入和增量讨论。
把间隔排序理解为多条子序列
间隔 gap=3 时,下标0、3、6构成一条子序列,下标1、4、7构成另一条。每条都执行插入排序,让远处逆序提前跨越较大距离,随后逐渐缩小间隔。
最后必须包含 gap=1,才能保证全局有序。不同间隔序列的性能和理论界不同,不能用一个序列的界描述所有 Shell 排序;远距离移动也通常破坏稳定性。
03把一个小例子完全算清楚
[8,5,3,1],间隔依次为 2、1。
| 步骤 | 计算与状态 | 为什么这样做 |
|---|---|---|
| gap=2,i=2 | 比较 3 与 8,得 [3,5,8,1] | 子序列下标 0、2 有序 |
| gap=2,i=3 | 比较 1 与 5,得 [3,1,8,5] | 子序列下标 1、3 有序 |
| gap=1 | 插入 1、8、5,得 [1,3,5,8] | 现在才完成整体排序 |
窄屏可左右滑动表格,阅读完整计算与理由。
大间隔阶段建立的是局部顺序;最后一轮连接这些子序列。
04为什么这个方法成立
- 固定 gap 时,每次插入保持当前子序列前缀有序。
- 所有位置处理完后,整个数组 gap-有序。
- 最终 gap=1 覆盖完整数组,因而升序正确;前面各轮不会丢失元素。
05把推导翻译成代码
Python · 可独立运行的教学实现
def shell_sort(values):
a = list(values)
gap = len(a) // 2
while gap:
for i in range(gap, len(a)):
key, j = a[i], i
while j >= gap and a[j-gap] > key:
a[j] = a[j-gap]
j -= gap
a[j] = key
gap //= 2
return a逐个理解关键决定
j -= gap- 只沿当前子序列回退。
gap //= 2- 整数减半保证最后到 1,再到 0 退出。
06时间、空间与实现范围
本减半增量的保守最坏界 O(n²),不能套用其他增量序列的界。
核心辅助空间 O(1),返回副本的本实现额外 O(n);通常不稳定。
07改变条件,检查哪里会出错
gap>1 时有序就提前结束
只能证明各子序列有序,必须执行 gap=1。
间隔变小就自动保持稳定
远距离移动会跨过相同键,稳定性没有保证。
遗漏最终间隔1
较大间隔内各自有序并不推出整个数组有序,最后一次普通插入阶段不可省略。
08从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
gap=2 的 [1,4,3,5] 是否整体有序?
需要一点提示
分别看偶数和奇数下标。
查看解析与答案
两条子序列分别为 [1,3]、[4,5],都已排序,但整体仍有 4>3。
n=9 的间隔是什么?
需要一点提示
反复整除 2。
查看解析与答案
4、2、1。
只执行 gap=1 会得到什么算法?
需要一点提示
比较代码内层。
查看解析与答案
普通插入排序,失去大间隔预处理。