c++oding="utf-8" ?>
std::sort是首选因其底层为introsort，融合快排、堆排和插入排序，平均与最坏时间复杂度均为o(n log n)，且经高度优化、安全稳定；手写快排易出错、易退化、难调试。
为什么 std::sort 是首选，而不是手写快排
绝大多数情况下，直接调用 std::sort 就是“快速排序”的正确实现方式——它底层通常用 introsort（混合快排+堆排+插入排序），既保证平均 O(n log n)，又避免快排最坏 O(n²) 的退化。手写快排不仅容易写错分区逻辑，还常因 pivot 选择不当、递归深度失控或边界条件处理失误导致崩溃或超时。
常见错误现象：std::sort 报错 segmentation fault，往往是因为传入了非法迭代器（如空数组却用了 arr, arr + n 而 n=0）；或者自定义比较函数没满足严格弱序（比如用了 而非 <code>）。
- 对内置类型（
int、double）直接用：std::sort(arr, arr + n) - 对
std::vector：用std::sort(vec.begin(), vec.end()) - 需要降序？传入
std::greater<int>()</int>或 lambda：[](int a, int b) { return a > b; } - 自定义结构体排序时，确保比较函数返回
false当两元素相等（即不满足a 且不满足 <code>b ）
手写快排时 pivot 怎么选才不容易崩
选错 pivot 是手写快排超时或栈溢出的主因。用首/尾元素当 pivot 在已排序或逆序数组上会退化成 O(n²)；用随机数又引入额外开销且不便于调试。
推荐三数取中法（median-of-three）：取首、中、尾三个元素的中位数作为 pivot。它能在多数实际数据分布下有效抑制退化，且无需随机数生成器。
- 对小数组（比如长度 ≤10），直接用插入排序代替递归——减少函数调用开销，也避免深度递归
- 递归前先处理较短的子区间，再用循环处理较长的——可将最坏递归深度从 O(n) 降到 O(log n)
- 分区时用双指针（
i从左找 ≥pivot，j从右找 ≤pivot），注意i 判断和交换时机，否则易越界或漏排
std::sort 和手写快排的性能差异到底在哪
差异不在“是否快排”，而在工程细节。libstdc++ 和 libc++ 的 std::sort 做了大量优化：内联分支预测、缓存友好的内存访问、混合算法切换阈值、尾递归消除、甚至 SIMD 加速的小范围排序。
实测在 10⁵ 级别随机 int 数组上，std::sort 比典型手写快排快 1.2–1.8 倍；在接近有序数据上，优势更明显（因它自动切到插入排序）。
- 若排序对象很大（如大结构体），考虑传引用比较：
[](const MyStruct& a, const MyStruct& b) { ... } - 避免在比较函数里做耗时操作（如字符串
.length()反复调用），提前缓存 - 编译时加
-O2或-O3对std::sort提升显著；手写快排若没内联关键函数，反而可能被优化器绕过
什么时候真得自己写快排
只有两种情况值得手写：一是教学/面试考察分区思想；二是嵌入式等极端环境（无 STL 支持，且必须控制栈空间或禁止动态内存）。其他所有场景，优先用 std::sort。
最容易被忽略的一点：快排不是稳定排序。如果需要保持相等元素的原始顺序，得换 std::stable_sort（通常是归并实现），或者给元素加原始索引再复合排序。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
