希尔排序的核心是分组插入：每轮按gap将数组划分为gap个子序列，对每个子序列做直接插入排序；下标满足i≡r(mod gap)，r∈[0,gap−1]；推荐Knuth序列（gap=3×gap+1）而非简单折半。

希尔排序的核心是分组插入，不是简单地“缩小增量”

很多人误以为希尔排序只是把 gap 从大到小变一变，其实关键在于：**每轮按当前 gap 将数组划分为 gap 个子序列，对每个子序列做直接插入排序**。考研题常考这个逻辑，而不是单纯套公式。

常见错误是写成“对整个数组扫一遍然后减 gap”，结果变成伪希尔（实际退化为低效冒泡）。正确做法必须保证：同一子序列的下标满足 i ≡ r (mod gap)，其中 r ∈ [0, gap-1]。

• 推荐初始 gap = n / 2，后续用 gap /= 2（虽然不是最优，但考研最常考、最易理解）
• 每轮内层循环要从 gap 开始，逐个将 a[i] 插入其所在子序列的已排序部分
• 子序列内插入时，比较和移动步长固定为 gap，不是 1

考研高频实现：使用 Knuth 序列更稳妥

纯除以 2 的序列（如 8→4→2→1）在某些输入下性能退化严重；而考研真题近年倾向考察更稳健的增量序列，比如 Knuth 序列：gap = gap * 3 + 1 反向生成（即先算出最大 gap ，再每次 gap = (gap - 1) / 3）。

原因：Knuth 序列能更好打乱局部有序性，避免小增量时大量移动。而且它天然保证最后一步是 gap == 1，无

int gap = 1;
while (gap < n) gap = gap * 3 + 1;
while (gap > 1) {
    gap /= 3;
    for (int i = gap; i < n; ++i) {
        int tmp = a[i];
        int j = i;
        while (j >= gap && a[j - gap] > tmp) {
            a[j] = a[j - gap];
            j -= gap;
        }
        a[j] = tmp;
    }
}

容易被忽略的边界和细节

考研代码题扣分点往往不在主干，而在细节处理：

• while (j >= gap && a[j - gap] > tmp) 中的 j >= gap 不能写成 j > gap，否则 j == gap 时跳过合法比较
• 内层循环变量 j 必须定义在 for 外（或 C++17 前需注意作用域），否则每次迭代重置，无法完成子序列内连续后移
• 如果题目要求稳定排序，希尔排序本身**不稳定**（相同值可能因跨组移动而交换相对位置），这点必须明确写出结论，不能回避
• 时间复杂度写法要严谨：平均 O(n^1.3)，最坏 O(n²)，不能只写“O(n log n)”——那是错的

调试时怎么验证自己写对了？

光跑通样例不够。建议手动模拟小数组（如 {9, 1, 2, 5, 7, 3, 4, 6, 8}，n=9），走一遍 Knuth 序列：gap 初始为 4（因为 1→4→13>9，取4），然后 1。

第一轮（gap=4）应产生四组： {9,7,8}、{1,3}、{2,4}、{5,6}，各自插入排序后变为 {7,1,2,5,8,3,4,6,9} —— 注意不是全局重排，而是组内有序。

第二轮（gap=1）就是普通插入排序，最终有序。如果某步结果不符合这个分组逻辑，说明内层循环步长或起始点错了。