希尔排序的核心是分组插入：每轮按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 ，再每次 <code>gap = (gap - 1) / 3）。
原因：Knuth 序列能更好打乱局部有序性，避免小增量时大量移动。而且它天然保证最后一步是 gap == 1，无需额外判断。
立即学习“C++免费学习笔记（深入）”；
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）就是普通插入排序，最终有序。如果某步结果不符合这个分组逻辑，说明内层循环步长或起始点错了。
