希尔排序应选Knuth序列（h=3h+1），避免n/2递减等劣质序列；循环下标从gap开始防越界；不用于std::sort因最坏复杂度不可证、缓存差且不稳定；仅适用于嵌入式或教学等特定场景。
希尔排序的增量序列怎么选才不慢
选错增量序列，希尔排序可能比插入排序还慢，甚至退化成 O(n²)。Knuth 序列 h = 3*h + 1（从 1 开始生成，取小于 n 的最大值）是实操中最稳的选择，兼顾实现简单和实际性能。
- 别用原始 Shell 提出的
n/2, n/4, ..., 1：相邻增量有公因数，大量元素位置不变，跳过太多比较 - 避免递减过快（如
n/3, n/9, ...）：分组太粗，后期插入排序负担重 - C++ 中推荐预生成增量数组，而非每次计算：减少重复除法，也方便调试
gap值
如何写一个不越界的希尔排序循环
下标越界是 C++ 实现里最常触发 std::out_of_range 或静默内存踩踏的地方，核心在内层插入排序的起始点和步长控制。
- 外层
for控制gap，内层for必须从gap开始（不是 0），否则i - gap会负溢出 - 内层循环条件写成
i 而非 <code>i + gap ：因为我们要对每个 <code>i做“向左跨 gap 插入”，不是“向右找下一个” - 移动元素时用
std::move（C++11+）替代拷贝：对自定义类型能明显提速，但注意类型得支持移动语义
for (int gap = h; gap > 0; gap /= 3) {
for (int i = gap; i < n; ++i) {
auto tmp = std::move(arr[i]);
int j = i;
while (j >= gap && arr[j - gap] > tmp) {
arr[j] = std::move(arr[j - gap]);
j -= gap;
}
arr[j] = std::move(tmp);
}
}
为什么 std::sort 不用希尔排序
希尔排序在现代 C++ 标准库中缺席，不是因为它错，而是它在通用场景下被更优解覆盖。
- 最坏时间复杂度仍不明确（已知下界 O(n^{1.5})，上界依赖增量序列），而
std::sort要求可证明的 O(n log n) - 缓存局部性差：
gap大时访问跨度大，CPU 预取失效，实测在 >10k 元素时往往输给 introsort - 不稳定：相同值可能因跨 gap 移动而交换顺序，而
std::stable_sort明确要求稳定
什么时候真该手写希尔排序
它没被淘汰，只是适用面窄——你遇到以下任一情况，才值得掏出它：
立即学习“C++免费学习笔记（深入）”；
- 嵌入式环境无 STL 支持，且数据量在 1k–100k、基本有序（比如传感器连续采样值）
- 需要比冒泡/选择更快，但又不想引入额外内存（归并不行）、不需稳定（堆排也不行），这时希尔是极简高性能折中
- 教学或面试：考察对“分组插入”思想的理解，而非工程选型
增量序列选错、边界写崩、忽略移动语义，这三个点卡住大多数人。调通之后你会发现，它真就只是带 gap 的插入排序——不多也不少。
