希尔排序
希尔排序（Shell Sort，又叫缩小增量排序 / Diminishing Increment Sort）是插入排序的推广——由 Donald Shell 于 1959 年提出，是最早突破 O(n²) 的排序算法之一。它的核心思想极其巧妙：插入排序对「近乎有序」的数组极快（接近 O(n)），但对「相距终位很远」的元素只能一步步相邻交换，效率被拖垮；希尔排序引入一个间隔（gap），先让相距 gap 的元素分组做插入排序（跨距离交换让元素快速跳到接近终位），再把 gap 逐步缩小到 1（最后一次就是普通的插入排序，此时数组已近乎有序，一遍扫完即可）。这个「先粗调后微调」的过程，让希尔排序在实际中等规模数据上比插入快得多、比快排更简单。
希尔排序的全部考点都源于一个关键事实：gap 序列决定复杂度。由此衍生出三大主题：①分组插入的本质——按 gap 把数组拆成 gap 个交错子序列各自插入排序，gap 从大到小缩到 1；②为何能突破 O(n²)——跨距离交换让元素一次跨越多步接近终位，不像插入排序只能相邻挪动，平均复杂度降到约 O(n^1.3)（依赖 gap 序列）；③gap 序列的选择——Shell 原版（n/2, n/4, …, 1）最坏仍 O(n²)，Knuth 序列（1, 4, 13, 40, …，h = 3h+1）最坏 O(n^1.5)，Sedgewick 序列进一步把平均压到 O(n^(4/3)) 左右。它是原地、不稳定的比较排序，最好 O(nlog²n) ~ O(nlogn)、平均 O(n^1.3)，是理解「如何把简单算法推广出亚二次复杂度」的经典案例。
评价
优点
- 突破 O(n²)：通过 gap 分组让元素跨距离交换快速接近终位，平均复杂度约 O(n^1.3)——比插入排序的 O(n²) 快一个量级，是早期少数能突破二次界线的算法之一
- 实现简单：在插入排序基础上加一层 gap 循环即可，代码不到 20 行，远比快排/归并的分区或递归简单——适合嵌入式、资源受限或中等规模数据场景
- 原地排序（in-place）：只需 O(1) 额外空间（几个临时变量），不需要归并的 O(n) 辅助数组
- 对中等规模数据实用：在 n 为几百到几千时，希尔排序的常数小、无递归开销，实测常常快于 O(n log n) 的堆排，甚至接近快排——很多库排序对小数组切到的「最后一公里」就用希尔或插入
缺点
- 复杂度依赖 gap 序列：不同 gap 序列性能差异巨大——Shell 原版最坏仍 O(n²)，Knuth 最坏 O(n^1.5)，Sedgewick 才能压到 O(n^1.3) 左右；没有「完美」序列，至今仍是数学未完全解决的问题
- 不稳定：分组后相等元素可能被分到不同子序列跨段交换，相对次序被打乱——需要稳定排序的场景（多关键字排序）要用归并或 Timsort
- 渐近复杂度不如快排/归并：最好的 gap 序列也只能到 O(n^1.3) 量级，数据量很大时仍慢于 O(n log n) 的快排/归并/堆排——大规模数据不是它的主场
本叶地图
- 入门 —— 分组插入思想、gap 从大到小缩到 1、为何比插入快（跨距离交换）、gap=1 即插入排序、与插入排序的关系
- 间隔序列 —— Shell 原版（n/2）、Knuth 序列（3k+1）、Sedgewick 序列、为何 gap 序列决定复杂度、各序列性能对比与代码实现
- 性能分析 —— 为何能突破 O(n²)、平均 O(n^1.3)、最好 O(nlog²n) ~ O(nlogn)、不稳定、为何中等规模实用、与各排序对比
- 参考 —— 复杂度表（依赖 gap 序列）、各 gap 序列对比、代码模板、与插入/快排对比、易错点
交互演示
- 希尔排序可视化演示 —— gap 从大到小分组插入的全过程