把一组乱序数字丢给 shellsort，它不会像冒泡那样傻乎乎地相邻交换。数字核心操作是序按按增量分组，组内做插入排序，数字增量一步步缩小，序按最终变成普通插入排序——但这时候数组已经“几乎有序”了，数字插入排序跑得飞快。序按我拿 [84,数字 12, 45, 3, 99, 27, 61, 8] 试了一下，增量选 4,序按 2, 1，整个过程三趟就收工，数字第三趟几乎没怎么挪动元素。序按

先看增量 4 的数字时候发生了什么。数组被切成 4 组：(84,序按 99)、(12,数字 27)、(45,序按 61)、(3, 8)。每组只有俩元素，直接比大小决定要不要换。结果 84 和 99 不用动，12 和 27 也不用，45 和 61 不用，3 和 8 不用——这一趟等于白跑。但别急，增量缩小到 2 才有好戏。

# 增量4之后（没变） [84, 12, 45, 3, 99, 27, 61, 8] # 增量2：分组 (84,45,99,61) 和 (12,3,27,8) # 第一组插入排序后：45, 61, 84, 99 # 第二组插入排序后：3, 8, 12, 27 # 合并回原位置： [45, 3, 84, 8, 61, 12, 99, 27] # 等等，这里我手算错了，实际应该是... 

上面那步我写岔了。重新来：增量 2 时，索引 0、2、4、6 是一组：84, 45, 99, 61。插入排序过程——45 比 84 小，换；99 不动；61 比 99 小，往前挪到 84 后面？不对，61 比 84 小，所以 84 后移，61 插到 84 前面。这组变成 45, 61, 84, 99。索引 1、3、5、7 是另一组：12, 3, 27, 8。3 比 12 小，换；27 不动；8 比 27 小，比 12 小，插到 12 前面，变成 3, 8, 12, 27。整个数组现在是 [45, 3, 61, 8, 84, 12, 99, 27]。比一开始好多了，至少大数往右跑了。

最后一趟增量 1，就是标准插入排序。但此时数组已经“基本有序”——45 和 3 要换，61 和 8 要换，84 和 12 要换，99 和 27 要换。每个元素最多往前挪两三个位置，不像原始插入排序那样一次挪十几步。我数了一下，增量 1 这趟总共只做了 4 次交换。如果一开始就用插入排序，光把 3 从索引 3 挪到索引 0 就得 3 次，把 8 从索引 7 挪到索引 1 得 6 次，加起来远超 4 次。

拿 Python 写个最简版，十行不到。注意增量是 gap //= 2，每次折半。内层用 while 做插入，比 for 循环写起来干净。

def shellsort(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 print(shellsort([84, 12, 45, 3, 99, 27, 61, 8])) # [3, 8, 12, 27, 45, 61, 84, 99] 

跑一下，输出正确。注意 arr[j - gap] > temp 这个比较——它决定了升序还是降序。想从大到小排，把 > 改成 < 就行。shellsort 不是稳定排序，相同数字的相对位置可能被打乱。比如 [5a, 3, 5b, 1] 排完可能变成 [1, 3, 5b, 5a]。如果你需要稳定，老老实实用归并或者 Timsort。

有人问为什么不用快排？快排平均 O(n log n) 确实更快，但 shellsort 代码短、不需要递归、原地排序、对中小规模数据（几千到几万）表现稳定。嵌入式环境或者脚本里随手写一个，比调库还方便。我有时候在 shell 脚本里用 awk 处理日志，需要排序但不想起 python 进程，就直接手写个 shellsort 塞进去——反正 awk 的数组也能模拟。

最后提一句增量序列的坑。如果你用 gap = gap // 2 且 n 是 2 的幂，某些输入会退化成 O(n²)。比如 n=8，增量 4,2,1 看起来没问题，但 n=16 时增量 8,4,2,1 可能让奇数位置和偶数位置一直不交叉，直到最后一趟才大量移动。解决办法是用 Knuth 序列 1, 4, 13, 40... 或者干脆在 gap 为偶数时加一。不过日常写业务代码，谁在乎那点最坏情况——数据量小，能跑就行。