std::sort 比手写快排快，因其采用 introsort（快排+堆排序降级+小数组插入排序）、抗恶意输入的 pivot 策略及编译器优化；三路快排仅适用于高重复数据的手动优化场景。
std::sort 为什么比手写快排还快？
因为 std::sort 在绝大多数标准库实现（如 libstdc++、libc++）里根本不是纯快排，而是 introsort —— 它在递归深度超阈值时自动切到堆排序，避免最坏 O(n²)；同时对小数组（通常 ≤16 元素）切到插入排序，省掉递归开销和 pivot 选择成本。
手写普通快排容易卡在重复元素多或已近序的场景，而 std::sort 还内置了三数取中 + 伪随机化 pivot 偏移，抗恶意输入能力更强。
实操建议：
- 除非你明确知道数据分布（比如大量重复值），否则别自己重写排序，直接用
std::sort - 确认编译器优化等级：-O2 或 -O3 下
std::sort会被内联+向量化部分分支，-O0 下性能可能断崖下跌 - 若需稳定排序，用
std::stable_sort，但它底层可能是归并，内存开销更大
三路快排适合什么场景？
当你面对大量重复键值（比如日志按状态码排序、数组含成千上万个相同整数），三路快排能把 partition 拆成 high 三段，把重复元素“一锅端”挤在中间，递归只处理两边，时间复杂度趋近 O(n)。
立即学习“C++免费学习笔记（深入）”；
但它的常数因子比双路快排高，且 std::sort 并不暴露三路接口 —— 所以它不是用来替代 std::sort 的，而是你在特定场景下手动优化的备选。
常见错误现象：std::partition 写两遍模拟三路，结果迭代器失效或边界越界；或者没处理好相等元素的移动方向，导致不稳定或死循环。
实操建议：
- 仅当 profiling 确认排序热点且输入满足“高重复率”（比如 >30% 元素重复）时再考虑
- 用
std::nth_element配合自定义三路划分逻辑，比从头手写更安全 - 注意迭代器类型：
std::vector可随机访问，std::list就别硬套三路快排了
introsort 的递归深度阈值怎么调？
libstdc++ 里默认是 2 * floor(log2(n))，n 是待排序长度。超过就退化为堆排序。这个值不能直接改 —— 它是编译期硬编码在 __introsort_loop 实现里的，用户无权干预。
想绕过？可以封装一层：先判断 n，若小于某个值（比如 1000）走 std::sort，否则手动分块 + std::partial_sort 控制深度，但这通常得不偿失。
性能影响很实际：设阈值太小，堆排序调用频繁，失去快排局部性优势；设太大，栈溢出风险上升（尤其嵌入式或协程环境 stack size 小）。
实操建议：
- 不要试图 patch 标准库源码去改阈值 —— 升级工具链后就失效，且破坏 ABI 兼容性
- 如果真遇到栈溢出（
std::bad_alloc或 SIGSEGV 在 sort 调用栈），优先检查是否误传了非法迭代器范围，而不是怀疑阈值 - 对极端大数组（>1e8 元素），考虑外排序或分块 map-reduce，而非调优 introsort
自定义比较函数怎么避免踩坑？
这是最容易让 std::sort 行为异常的地方。标准要求比较函数必须满足 strict weak ordering：不可自反（a 必须为 false）、不可矛盾（若 <code>a 且 <code>b ，则 <code>a ）、等价类必须可传递。
常见错误现象：程序在 -O2 下崩溃、排序结果每次运行不一致、甚至触发 std::terminate（GCC 检测到非法比较会 abort）。
实操建议：
- 别用
float或double做 key 比较，用std::abs(a - b) 会破坏传递性；改用 <code>std::round后转整型，或用std::numeric_limits<double>::epsilon()</double>配合std::lexicographical_compare - lambda 捕获外部变量时，确保生命周期长于 sort 调用 —— 悬垂引用会导致未定义行为
- 调试时加个 assert：
assert(!comp(x, x));，在开发版强制校验
三路快排和 introsort 的核心差异不在“谁更快”，而在“谁更鲁棒”。标准库的选择已经覆盖了绝大多数现实负载，手动介入往往是在补 profiler 暴露的明确缺口，而不是凭直觉替换。真正容易被忽略的是：比较函数的数学性质，和编译器优化对 sort 内联的影响 —— 这两点不验证，其他优化都可能白做。
