排序算法全族
环境：Windows 11 x64，GCC 13.1.0，
g++ -std=c++17 -O2。6 种实现先在 6 类数据上与std::sort逐一比对确认排对，再计时。
一、先确认排对了
6 种实现 × 6 类数据全部与 std::sort 一致=1六类数据是刻意选的：完全随机、已升序、完全逆序、全部相等、只有 5 个不同值、多重复段。只测随机数据的话，快排的 O(n²) 退化、堆排的边界错误、归并的缓冲区错位全都测不出来。
二、耗时实测（500 万个 int，单位 ms）
| 数据分布 | 希尔 | 堆排 | 归并 | 三路快排 | 基数 LSD | std::sort |
|---|---|---|---|---|---|---|
| 完全随机 | 850.4 | 926.3 | 450.2 | 406.5 | 58.9 | 329.2 |
| 已升序 | 128.8 | 300.0 | 71.5 | 98.8 | 158.5 | 51.2 |
| 完全逆序 | 143.6 | 337.8 | 93.5 | 97.7 | 158.2 | 40.6 |
| 全部相等 | 117.2 | 143.7 | 82.9 | 4.2 | 87.5 | 46.2 |
| 只有 5 个不同值 | 213.8 | 285.2 | 175.3 | 43.5 | 80.3 | 95.6 |
| 多重复段 | 115.7 | 446.1 | 81.1 | 49.2 | 82.6 | 38.4 |
（插入排序在 500 万上是 2.5×10¹³ 量级的操作，估算是几十分钟，跳过；它在 5000 规模上与其他实现全部排对。）
四个必须记住的读数：
- 基数排序在整数键上碾压一切：58.9ms，是
std::sort的 1/5.6。因为它根本不做比较——O(w·n)，字长固定就是线性。代价：只适用于可映射成定长键的数据，且要额外缓冲区（这里 500 万 int = 20MB）。 - 三路快排在”全部相等”时是 4.2ms，比
std::sort快 11 倍。因为等于 pivot 的元素被一次性归到中间、不再递归。这是处理”大量重复键”的关键设计，也是为什么很多库排序近年从二路换成三路。 std::sort（introsort）在所有非特殊场景都接近最快：它 = 快选 + 堆排兜底 + 小数组转插入，工程调优到位。默认就该用它。- 堆排在随机数据上最慢（926ms），尽管它也是 O(n log n)：每次
pop_heap都要从顶沉到底，访问模式是跨大步的，缓存极不友好。理论比较次数少，实测完全不是对手。
三、稳定性：我的第一版测试是错的
正确的测法是只用 key 比较（允许相等），然后检查相等元素的下标是否仍递增：
std::sort（introsort） 稳定=0
std::stable_sort（归并） 稳定=1
heapsort（key-only 比较） 稳定=0
三路快排（key-only 比较） 稳定=0
std::sort 用 pair 默认比较 稳定=1 ← 假象！最后一行是我的第一版实现：用 pair<key, 原始下标> 的默认比较排序，第二键自动打破了所有平局，于是任何排序都”看起来稳定”。
这不是纯粹的失误，而是一个正当的技巧：想在不稳定的排序上获得稳定结果，就把原始下标附加进比较键（(key, index)）。代价是比较变贵、元素变大。反过来说：如果你需要稳定性，要么用 std::stable_sort，要么显式加下标当第二键，别指望 std::sort。
什么时候真的需要稳定？多关键字排序（先按部门、再按工号，分两次排且第二次必须稳定）、保持原始输入顺序的报表输出、以及”相等元素的其它字段有意义”的场景。
四、std::sort 到底做了什么（introsort）
libstdc++ 的 std::sort 是三段组合，实测能验证每一段：
- 快排主体：median-of-3 或更复杂的 pivot 选择，避免有序输入退化。
- 证据：已升序 51.2ms、完全逆序 40.6ms、随机 329ms——有序数据反而更快，因为分支预测友好，说明它没有被退化惩罚。
- 深度限制：递归超过
2·log₂n层就切换到堆排，保证最坏 O(n log n)。这就是”introsort”的名字来源（introspective）。 - 小区间切换插入排序：长度小于阈值（libstdc++ 是 16）时用插入排序。
第三点的实测证据（30 万次排序，每次 n 很小）：
n= 8 插入排序 36 ms | std::sort 36 ms
n=16 插入排序 70 ms | std::sort 67 ms
n=32 插入排序 148 ms | std::sort 189 ms
n=64 插入排序 360 ms | std::sort 416 msn≤16 时两者持平（因为 std::sort 内部本来就走插入），n=32/64 时我的纯插入排序反而更快（std::sort 在这个尺度上还多做了 partition 的开销）。
为什么 O(n²) 的插入排序在小数组上赢？ 因为它的每次比较都是顺序内存访问 + 高度可预测的分支，而快排要做 pivot 选择、递归调用、跨距离交换。大 O 忽略的常数在小尺度上成了主导。
五、各算法的定位（一张决策表）
| 算法 | 时间（平均/最坏） | 空间 | 稳定 | 什么时候用 |
|---|---|---|---|---|
| 插入 | O(n²) / O(n²)，近有序时 O(n+k) | O(1) | ✅ | 小数组（<16）、近乎有序、在线插入 |
| 希尔 | 取决于增量序列，约 O(n^1.3) | O(1) | ❌ | 无栈空间限制、不要稳定性（嵌入式里偶尔用） |
| 堆排 | O(n log n) / O(n log n) | O(1) | ❌ | 必须原地 + 必须最坏保证时（嵌入式、实时系统） |
| 归并 | O(n log n) / O(n log n) | O(n) | ✅ | 需要稳定、链表排序、外部排序 |
| 快排（三路） | O(n log n) / O(n²) | O(log n) | ❌ | 通用；重复键多时三路明显更好 |
| introsort | O(n log n) / O(n log n) | O(log n) | ❌ | 就是 std::sort，默认选择 |
| 基数 LSD | O(w·n) / O(w·n) | O(n+k) | ✅（按位稳定） | 定长整数/可映射成定长键；n 大时最快 |
| 计数 | O(n+k) / O(n+k) | O(k) | ✅ | 值域 k 很小（成绩分布、直方图） |
partial_sort | O(n log k) | O(k) | — | 只要前 k 个且要有序 |
nth_element | O(n) 平均 | O(1) | — | 只要前 k 个、不要求有序（中位数、Top-K） |
六、下界与”能不能更快”
- 比较排序的下界是 Ω(n log n)（决策树有 n! 个叶子，log₂(n!) ≈ n log n）。所以
std::sort的 329ms 已接近极限。 - 要突破它只能利用”键的结构”：基数排序、计数排序不是比较排序，它们用 O(w·n) 换掉了 log n。这就是实测里基数排序快 5.6 倍的全部原因。
- 推论：当你能把排序键压成定长整数（或可字典序比较的字节串）时，基数排序是数量级级别的优化。数据库的 fixed-width key 排序、编译器符号表排序都吃这个红利。
- 另一个方向是并行：C++17 的
std::execution::par让std::sort变成并行归并/快排，多核线性加速（需要 TBB）。
七、这一节的自查清单
- 默认用
std::sort；需要稳定用std::stable_sort，或把下标加进比较键 - 只要前 k 个用
nth_element（不要求有序）或partial_sort，不要全排 - 值域小或键定长 → 计数/基数排序，能拿到数量级收益
- 测试数据必须包含：已排序、逆序、全相等、少量不同值、含重复段
- 测稳定性时比较器只能看 key，加了第二键的测试是无效的
- 手写快排要用三路划分，否则重复键会退化成 O(n²)
- 递归快排要有深度保护（tail-call 优化 + 堆排兜底），否则对抗性输入能撑爆栈
- 比较函数里绝不做重活（缓存、字符串构造），
std::sort会调用它 n log n 次 - 记住堆排的理论优势在真实机器上会被缓存惩罚吃掉
下一节讲哈希表与冲突处理：除留余数与乘法散列的分布实测、开放寻址 vs 链地址、负载因子与 rehash 的代价、以及 std::unordered_map 的四个性能陷阱。