希尔排序 Shell Sort

插入排序 · 用大间隔跳出 O(n²)

什么是希尔排序

希尔排序是插入排序的加速版。插入排序每次只和相邻元素比较，一个远在末尾的小元素要一格格挪很久。希尔的点子是：先用一个大的「间隔 gap」把数组分成若干组（每隔 gap 个取一个元素为一组），对每组各自做插入排序——这样元素能大步跨越、快速接近最终位置；然后缩小 gap 再来一轮，直到 gap=1 做最后一次普通插入。此时数组已「基本有序」，最后一趟极快。

它怎么做

外层 gap 逐轮减半（如 5 → 2 → 1），每个 gap 下对各分组做插入排序。点「下一步」看 [7, 6, 5, 10, 9, 8, 4, 3, 2, 1]：当前正在处理的那一组柱子高亮、其余淡出（dimmed）——你能清楚看到「隔着 gap 的元素凑成一组比较」，以及大间隔如何让逆序对被快速消除。

复杂度与适用

希尔排序不稳定、原地，时间复杂度取决于 gap 序列——本页用的减半序列约 O(n²) 最坏，而 Knuth、Sedgewick 等精心设计的序列可达 O(n^1.3) 上下。它是第一个突破「相邻交换类 O(n²)」的排序，证明了「先粗调、再细调」这一思路的威力；工程上偶尔用于中等规模、又想避免递归/额外内存的场景。

建议先看插入排序页，再回来体会希尔怎么用「间隔」给它提速；同一族的还有 二分插入排序（从比较次数下手优化）。