推荐使用 std::sort，因其底层采用优化的 introsort 混合策略，兼顾效率与稳定性，避免手写递归快排的 O(n²) 退化、栈溢出及小数组性能差等问题。
快速排序在 C++ 中最实用的实现方式是用 std::sort，它底层通常是优化过的 introsort（内省排序），不是纯快排，但比手写递归快排更安全、更快、更少栈溢出风险。
为什么别直接手写递归快排
手写经典递归快排看似简单，实际容易踩坑：
- 最坏情况（已排序数组）下时间复杂度退化为
O(n²)，且默认 pivot 取首/尾元素时极易触发 - 深度递归导致栈溢出——比如排序 10⁶ 个元素时，递归深度可能超千层
- 小数组性能差：函数调用开销、分支预测失败，不如插入排序
- 三路划分、尾递归优化、median-of-three 等改进点分散在各处，自己拼容易漏
std::sort 是什么，为什么推荐用它
std::sort 是 C++ 标准库提供的泛型排序算法，定义在
- 对大数组：先用 introsort（快排 + 堆排序 fallback）防止退化
- 对小数组（通常 ≤32 元素）：自动切换为插入排序
- 对重复值多的数组：部分实现（如 libstdc++）会检测并启用三路划分逻辑
- 支持自定义比较器，且对迭代器类型无额外要求（只要满足 RandomAccessIterator）
示例：
立即学习“C++免费学习笔记（深入）”；
#include#include std::vector
v = {3, 1, 4, 1, 5, 9, 2, 6}; std::sort(v.begin(), v.end()); // 升序 std::sort(v.begin(), v.end(), std::greater {}); // 降序
如果真要手写快排，关键优化点在哪
仅限学习或特殊场景（如嵌入式无 STL）。必须包含以下三点，否则不叫“高效”：
-
随机 pivot 或 median-of-three：避免 worst-case。不要用
v[l]或v[r]，改用v[(l+r)/2]或三数取中 -
尾递归优化：对较小的子区间先递归，较大的子区间用循环处理，压栈深度从
O(n)降到O(log n) -
小数组切回插入排序：当
r - l 时，调用一个内联插入排序函数
片段示意（pivot 随机化 + 尾递归）：
void quick_sort(std::vector& v, int l, int r) { while (l < r) { int p = partition(v, l, r); // 返回 pivot 最终位置 if (p - l < r - p) { quick_sort(v, l, p - 1); l = p + 1; } else { quick_sort(v, p + 1, r); r = p - 1; } } }
性能对比和实际建议
在现代 x86-64 编译器（GCC/Clang）+ O2 下：
-
std::sort比手写快排平均快 10%–30%，尤其在边界数据（全相同、已排序、逆序）上优势明显 - 手写快排调试成本高：partition 边界错一位就段错误或死循环，
l 还是l 容易混淆 - 若需稳定排序，别硬改快排——直接用
std::stable_sort，它用的是归并
真正需要“控制细节”的场景（比如教学、竞赛 debug、定制内存布局），才值得投入时间写带完整优化的手写版本；其他时候，std::sort 就是那个被反复验证过、编译器能 inline、CPU 能预测、缓存友好的答案。
