1. 为什么要跨距离插入？
普通插入排序一次右移一个位置；一个很小的元素若在末尾，可能要移动很多次。希尔排序先在远距离的分组里插入，再缩小距离，让数据逐步接近有序。
2. gap 与分组
gap=4 时，索引余数相同的元素组成一组：0,4,8,...、1,5,9,... 等。h 有序意味着每条间隔 h 的子序列有序，不代表整个数组已经有序。
3. 原书 4、2、1 的例子
初始 [55,74,3,45,13,87,46,30]。
- gap=4 后：
[13,74,3,30,55,87,46,45]。 - gap=2 后：
[3,30,13,45,46,74,55,87]。 - gap=1 后：
[3,13,30,45,46,55,74,87]。
每一轮是各个间隔子序列的插入排序。最后 gap=1 才保证整体有序。
4. 两种增量序列
def halving_gaps(n):
result = []
gap = n // 2
while gap:
result.append(gap)
gap //= 2
return result
def knuth_gaps(n):
if n < 2:
return []
gap = 1
while 3*gap+1 < n:
gap = 3*gap+1
result = []
while gap:
result.append(gap)
gap //= 3
return result
折半序列直观，但会让奇偶组较长时间不相混合。Knuth 序列来自 3h+1：1、4、13、40、121……，使用时逆序。本教材从小于 n 的最大项开始；原书采用 n/9 附近的起点，两者都属于教学选择，不必逐字复刻旧阈值。
5. Python 实现
def shell_sort(a, key=lambda x: x, gap_factory=knuth_gaps):
for gap in gap_factory(len(a)):
for i in range(gap, len(a)):
item = a[i]
j = i
while j >= gap and key(a[j-gap]) > key(item):
a[j] = a[j-gap]
j -= gap
a[j] = item
return a
j -= gap、a[j-gap] 是与普通插入排序的关键区别。item 暂存，组内只移动严格较大的记录。
6. 使用示例
a = [55,74,3,45,13,87,46,30]
print(shell_sort(a.copy(), gap_factory=halving_gaps))
print(shell_sort(a.copy(), gap_factory=knuth_gaps))
print(knuth_gaps(50)) # [40, 13, 4, 1]
7. 不稳定性并不会被最后一轮修复
对键和身份 [2A,2B,1X,3Y] 用 gap=2、1：第一轮让 1X 与 2A 跨位置移动，结果出现 2B 在 2A 之前；最后稳定的 gap=1 插入只能保留当时已经改变的相等键顺序。
8. 复杂度不能一概写成 n 的某次幂
性能依赖增量序列、数据分布和实现。经典折半序列的最坏情况可为 O(n²)。不同序列有不同的理论界和经验表现，因此不能把所有希尔排序统一写成 O(n^1.5)，也不能声称它永远优于插入排序。工作空间为 O(1)。
9. 循环不变式与验证
完成某个 gap 后，逐组检查 a[i-gap] <= a[i]。最终 gap=1 时，这就是全数组有序。增量必须为正，并最终包含 1。自定义序列若漏掉 1，算法可能只做到分组有序。
10. 常见错误
把 gap 当成连续分块长度；循环内仍然写 j−1；只看一次具体结果就认定稳定；把原书经验复杂度当成普适保证；认为最后 gap=1 会恢复原始相等键顺序。