希尔排序是什么？它是怎么改进插入排序的？

简化版

希尔排序是插入排序的改进版。插入排序每次只能交换相邻元素、移动很慢；希尔排序先用一个较大的间隔（gap） 把数组分成若干组，对每组做插入排序，然后逐步缩小 gap 直到 1（最后一轮就是普通插入排序）。大 gap 让元素能「大步跳跃」快速接近最终位置，等 gap 变小时数组已近乎有序,插入排序就很快。它突破了 O(n²),但不稳定。

详细版

void shellSort(int[] a) {
    int n = a.length;
    for (int gap = n / 2; gap > 0; gap /= 2) {   // gap 逐步减半直到 1
        for (int i = gap; i < n; i++) {           // 对每个 gap 间隔的组做插入排序
            int cur = a[i], j = i - gap;
            while (j >= 0 && a[j] > cur) {
                a[j + gap] = a[j];                // 按 gap 后移
                j -= gap;
            }
            a[j + gap] = cur;
        }
    }
}

gap 序列：常见从 n/2 开始每次减半（希尔原始序列），直到 gap=1。
每个 gap 下，对「间隔为 gap 的元素组」做插入排序（其实是把插入排序里的「1」换成「gap」）。
gap=1 的最后一轮就是标准插入排序,但此时数组已近乎有序,极快。

完整版教学

一、插入排序的瓶颈:只能挪一格

插入排序有个硬伤:它每次只能把元素和相邻元素交换/后移一格。如果一个很小的元素躺在数组最右边,要把它挪到最左边,得一格一格地移 n 步。当有很多这种「远距离逆序对」时,插入排序就慢(O(n²))。希尔排序的核心洞察是:能不能让元素先大步跳跃、快速接近目标位置,减少后面的小步移动?

二、希尔的思路:先粗排,再细排

希尔排序引入一个间隔 gap,把「相隔 gap 的元素」看成一组,对每组做插入排序:

gap 大时（如 n/2）:每组只有很少几个元素,但它们在原数组里相距很远。对它们排序,能让元素一次跳跃 gap 那么远,快速把「大范围的乱序」消除掉。
gap 逐步缩小:每缩小一次,分组变粗、组内元素变多,但因为前面大 gap 已经让数组「大致有序」了,插入排序移动很少。
gap=1 时:就是普通插入排序,但此时数组已经近乎有序,插入排序发挥它「近乎有序时接近 O(n)」的优势,飞快收尾。

一句话:用大 gap 快速消除大范围乱序,用小 gap 精细收尾,避开了插入排序「只能挪一格」的瓶颈。

三、走一个直觉例子

数组: [8, 5, 3, 7, 1, 9, 2, 6]  n=8
gap=4: 分成 4 组 {8,1}{5,9}{3,2}{7,6},各组插入排序
       → [1, 5, 2, 6, 8, 9, 3, 7]   (大范围乱序被快速消除)
gap=2: 分成 2 组 {1,2,8,3}{5,6,9,7},各组插入排序
       → [1, 5, 2, 6, 3, 7, 8, 9]
gap=1: 普通插入排序,此时已近乎有序,少量移动即完成
       → [1, 2, 3, 5, 6, 7, 8, 9]

四、复杂度:取决于 gap 序列

希尔排序的复杂度和 gap 序列的选择密切相关,分析很复杂:

希尔原始序列（n/2, n/4, …, 1）:最坏 O(n²)。
Hibbard 序列（1,3,7,…,2^k−1）:最坏 O(n^1.5)。
Sedgewick 序列等:可到约 O(n^1.3)。

所以希尔排序平均大致在 O(n^1.3) ~ O(n^1.5),明显优于插入排序的 O(n²),但达不到 O(n log n)。它的实际表现和 gap 序列强相关,是个「用简单代码换来不错性能」的折中。

五、为什么希尔排序不稳定

插入排序是稳定的,但希尔排序不稳定。原因:希尔排序在不同的分组里移动元素,相等的两个元素可能被分到不同的 gap 组、各自移动,它们的相对顺序就可能被打乱。跨组的远距离移动破坏了稳定性。

六、希尔排序的定位

优点:代码简单(就是带 gap 的插入排序)、原地 O(1) 空间、突破了 O(n²)、对中等规模数据表现不错。
缺点:不稳定;复杂度分析困难、依赖 gap 序列;比 O(n log n) 的快排/归并慢。
定位:是「简单排序」到「高效排序」之间的过渡,历史意义大(第一个突破 O(n²) 的排序),实际工程用得不多(有快排/归并),但面试常考它「如何改进插入排序」的思想。

七、把不变量、推演与工程边界落到代码上

算法正确性的核心不是记住某个 while，而是始终维护这个不变量：每个 gap 阶段结束后，所有相距 gap 的子序列都分别有序。

对应的状态推进是：对每个 gap 做分组插入排序，逐步缩小 gap，最后必须取 gap=1。每次推进前都应能解释“为什么被排除的部分不可能再包含答案”，否则只是碰巧通过样例。

初始化边界与状态
while 尚未结束:
    根据当前状态作出唯一可证明安全的选择
    更新边界、计数或局部结构
    断言不变量仍然成立
返回不变量在终止状态下推出的答案

复杂度不能只背一个符号。复杂度依赖增量序列；常见折半序列最坏可达 O(n²)，不能笼统写 O(n log n)。

带数字走一遍：[9,1,8,2,7,3] 用 gap=3 可先跨距离移动 9 和 2，减少最终逐格搬移。手算时要同时记录下标、区间含义和本轮排除的候选，才能暴露等号与边界错误。

核对项	结论
前提	适合中等规模、内存受限且不要求稳定的内部排序
时间复杂度	取决于 gap 序列，常见最好优于插入、最坏可 O(n²)
额外空间	O(1)
关键边界	gap 序列必须最终到 1；跨组移动会破坏相等元素顺序
替代方案	现代通用排序通常采用经过充分验证的混合算法

易错点：模板只有在前提和不变量一致时才成立；换了区间定义、重复值规则或输出语义，等号与推进方式就必须重新推导。

实现完成后至少检查五类用例：

空输入或题目允许的最小规模，验证初始化不会越界。
单元素与两个元素，验证循环条件和最后一次推进。
大量重复值，验证相等分支、稳定性或去重语义。
已满足目标性质与极端逆序/偏斜分布，观察最好和退化路径。
上面的数字样例逐轮手算，并与程序记录的状态轨迹逐项对照。

八、常见误区与追问

误区：只要记住模板就适用于所有输入。 本题成立的前提是“适合中等规模、内存受限且不要求稳定的内部排序”，前提被破坏后必须换算法或重新证明。
误区：复杂度只写取决于 gap 序列，常见最好优于插入、最坏可 O(n²) 就算完整。 还要说明输入参数、预处理、递归栈以及最坏退化条件；本题的推导是“复杂度依赖增量序列；常见折半序列最坏可达 O(n²)，不能笼统写 O(n log n)”。
误区：重复值和边界值不会改变代码。 gap 序列必须最终到 1；跨组移动会破坏相等元素顺序。
追问：为什么每次推进不会漏掉答案？ 因为始终维护“每个 gap 阶段结束后，所有相距 gap 的子序列都分别有序”，被舍弃区域已由顺序或状态关系证明不可能更优。
追问：用一个数字例子怎么讲？ 可以从“[9,1,8,2,7,3] 用 gap=3 可先跨距离移动 9 和 2，减少最终逐格搬移”开始，逐轮写出状态与被排除区间。
追问：什么时候不该使用这个方案？ 当前提不满足或退化代价不可接受时，应考虑“现代通用排序通常采用经过充分验证的混合算法”。
追问：如何设计自测避免只过样例？ 同时覆盖最小规模、重复值、极端分布、无解/边界解，并对关键状态加断言。

九、加强记忆

希尔排序是插入排序的改进:用间隔 gap 分组、对每组插入排序,gap 逐步缩小到 1(最后一轮即普通插入排序)。核心思想:大 gap 让元素大步跳跃、快速消除大范围乱序,小 gap 时数组已近乎有序、插入排序飞快收尾,避开了插入排序「只能挪一格」的瓶颈。突破 O(n²)(约 O(n^1.3~1.5),依赖 gap 序列)、原地 O(1)、但不稳定(跨组远距离移动打乱相等元素)。

简化版

详细版