Olverae Assets

1 先看：插入排序"挪一步太慢"，那就先"跳着挪"

普通插入排序每次只把元素往前挪一格。要是一个很小的数排在最右边，它得一格一格挪过整个数组，太慢。希尔排序（Shell Sort）的点子是：先按一个较大的间隔 gap 做插入排序（让元素一次跨 gap 格大步移动），再不断缩小 gap，最后 gap=1 时就是普通插入排序——但此时数组已经"基本有序"，几乎不用挪了。点「下一步」看每一轮 gap 怎么跑。

希尔排序单步演示（gap 序列 4 → 2 → 1）

点「下一步」：先用 gap = 4 这一大步，把相隔 4 的元素配成一组各自排序。

希尔排序：带间隔的插入排序。先用较大的 gap 让相隔 gap 的元素各自有序，再逐步缩小 gap 直到 1。

它是插入排序的"加速版"：大 gap 让元素快速移动到大致位置，小 gap 做精修；gap=1 时收尾的插入排序面对的是一个几乎有序的数组，因此很快。

2 凭什么更快：大步搬运 + 越来越接近有序

插入排序在"基本有序"的数组上是接近 O(n) 的。希尔排序的全部努力，就是让最后那次 gap=1 面对的数组尽量有序。

大 gap = 长距离搬运

gap=4 时，一次比较/移动就跨越 4 个位置。一个远在右端的小元素，几步就能跨到左边，不必一格一格爬。

每轮让数组更"有序"

每缩小一次 gap，数组的"逆序对"大幅减少。轮到 gap=1 时，逆序已经很少，插入排序只需做很少的局部微调。

原地、无需额外数组

和插入排序一样原地进行，只用常数级额外空间，不像归并排序要开辅助数组。

关键直觉：gap=1 那一轮本质上就是普通插入排序，正确性由它保证；前面的大 gap 轮只是"预热"，把数组揉得接近有序，从而让最后一轮跑得飞快。

3 gap 怎么选、有多快、稳不稳定

希尔排序的性能取决于 gap 序列——这也是它有趣又微妙的地方。

gap 序列	例子	大致最坏复杂度
Shell 原始（n/2, n/4, …, 1）	8, 4, 2, 1	O(n²)
Knuth（…, 13, 4, 1，即 3k+1）	13, 4, 1	≈ O(n^1.5)
Sedgewick 等更优序列	…, 41, 19, 5, 1	≈ O(n^4/3)

序列必须以 1 结尾（否则不能保证最终有序）。选得好能明显快于 O(n²)，但精确复杂度的数学分析至今没有完全定论——这正是它"简单却深刻"的地方。

不稳定：因为元素会跨越较大间隔交换位置，相等元素的相对先后可能被打乱。如果你需要"稳定排序"（保持相等元素原有顺序），希尔排序不合适，应选归并排序或稳定版本。它也不是比较次数最优的排序，但实现简单、原地、常数小，在中小规模或嵌入式场景很实用。

4 自测

三道题，点选项即时判对错。

去做例题：把数组升序排好（任选排序实现）

去做例题

一句话带走：

希尔排序 = 带间隔 gap 的插入排序：先用大 gap 做"跳着比"的插入，让元素大步就位、数组越来越接近有序，再逐步缩小 gap 到 1 收尾。正确性由 gap=1 那轮（普通插入排序）保证，速度来自前面的预热。性能取决于 gap 序列（Knuth 序列约 O(n^1.5)）；原地但不稳定。