希尔排序步长序列应避免相邻步长存在整除关系，推荐使用Knuth序列（h=3h+1），生成后需过滤掉≥数组长度的值，否则会退化为O(n²)。
希尔排序的步长序列怎么选才不退化成插入排序
选错步长会让 shell_sort 时间复杂度从平均 O(n^1.3) 退化到最坏 O(n^2)，和纯插入排序一样慢。关键不是“越大越好”，而是相邻步长之间不能有整除关系，否则部分子数组压根不会被重新比较。
实操建议：
- 新手直接用
Knuth 序列：h = h * 3 + 1，从1开始生成直到超过数组长度，再倒序使用（如1, 4, 13, 40...）——它天然避免公因数问题，实现简单且实测稳定 - 别用
gap = n/2, n/4, n/8...（希尔原始序列），在某些数据分布下会漏排，比如已按奇偶分组有序的数组 - 如果数组长度固定且已知，可以预计算好步长数组存为
const std::vector<int></int>，避免运行时反复除法或递归生成
C++ 实现中 for 循环边界容易写反的三个位置
希尔排序嵌套三层逻辑（步长循环 → 子数组起始点循环 → 插入比较循环），第二层和第三层的边界条件最容易出错，导致越界或跳过元素。
常见错误现象：std::out_of_range、排序后末尾几个元素不变、小数组完全没动
立即学习“C++免费学习笔记（深入）”；
实操建议：
- 外层步长循环用
for (int gap = max_gap; gap > 0; gap /= 3)，注意是gap > 0而不是gap >= 1（虽等价但易混淆） - 中间层子数组起点从
gap开始，不是0：因为[0, gap-1]是每个子数组的“首元素”，它们不参与当轮插入比较 - 内层比较循环的
j必须满足j >= gap才能访问arr[j - gap]，写成j > 0就会崩
为什么用 std::vector 而不是裸指针传参
裸指针 + 长度参数看似轻量，但实际增加了步长计算和边界检查的出错概率；而 std::vector 的 .size() 和迭代器语义更贴合希尔排序的动态分组逻辑。
性能影响其实极小：现代编译器对 std::vector 的 operator[] 基本做零开销抽象；而手动管理指针反而可能因忘记 const 修饰引发意外修改。
实操建议：
- 函数签名统一用
void shell_sort(std::vector<int>& arr)</int>，避免传int*+size_t组合 - 如果真要支持裸数组，用模板 +
std::span（C++20）或std::array更安全，而不是硬写指针算术 - 调试时直接用
arr.at(i)替代arr[i]可快速暴露越界——仅限开发期，发布前换回[]
测试时发现偶数长度数组排序错乱，大概率是步长没截断到 arr.size()
比如数组长 10，按 Knuth 序列 生成了 1, 4, 13，但直接拿 13 当第一轮步长就会让内层循环失效（j 根本进不去），结果退化为只跑 gap=4 和 gap=1 两轮，漏掉部分分组。
实操建议：
- 生成步长序列后，必须加一句过滤：
gaps.erase(std::remove_if(gaps.begin(), gaps.end(), [n](int g) { return g >= n; }), gaps.end()); - 更省事的做法：生成时就控制上限，例如
while (h ，然后 <code>std::reverse(gaps.begin(), gaps.end()) - 写个最小测试用例：
{5, 2, 4, 1}（长度 4），正确结果是{1, 2, 4, 5}；如果输出{2, 1, 4, 5}，基本就是步长过大没生效
步长序列不是随便递减就行，它决定了数据跨距重排的“视野范围”。写错一个 > 或漏掉一次 /= 3，整个排序就 quietly 失效——这种 bug 不报错，只悄悄错排。
