直接写递归快排易栈溢出，因最坏情况递归深度达O(n)，而C++默认栈仅1–8MB；应采用尾递归优化、小数组切插入排序、随机选基准等策略控深。
为什么直接写 partition 容易栈溢出
手写快速排序时，很多人照着教材实现一个递归版 quick_sort，但没注意最坏情况（如已排序数组）下递归深度达 O(n)，小数据量就可能触发栈溢出。C++ 默认线程栈通常只有 1–8MB，递归调用千层以上就危险。
关键不是“要不要快排”，而是“怎么控深”。实际应结合：
- 尾递归优化（对较小子区间先递归，较大子区间用循环处理）
- 当子数组长度 ≤ 10 时切到插入排序（减少函数调用开销 + 提升小数组性能）
- 随机选基准（std::uniform_int_distribution 或 rand() + swap）避免退化
std::sort 为什么比手写快？它用了什么
别急着重造轮子——std::sort 在大多数标准库（libstdc++、libc++）中是 introsort：起手快排，递归深度超阈值（通常为 2×log₂(n)）自动切到堆排序，最后用插入排序收尾。它还做了：
- 内联 __lg(n) 计算对数（非浮点运算）
- 分支预测友好的比较逻辑（避免 if 频繁跳转）
- 对 int 等 POD 类型启用底层内存操作（如 memmove）
除非你明确要控制 pivot 策略或适配自定义容器，否则直接用 std::sort(v.begin(), v.end()) 更稳更快。
一个安全可用的手写 quick sort 示例（含边界处理）
以下代码避开常见坑：
- 不用 int 做索引（改用 size_t 或 ptrdiff_t 防负溢出）
- partition 返回的是「等于 pivot 的右边界」，避免死循环
- 每次递归前检查区间长度，空或单元素直接 return
void quick_sort(std::vector<int>& a, size_t left = 0, size_t right = SIZE_MAX) {
if (right == SIZE_MAX) right = a.size();
if (right - left <= 1) return;
<pre class="brush:php;toolbar:false;">// 小数组切插入排序
if (right - left <= 10) {
for (size_t i = left + 1; i < right; ++i) {
int key = a[i];
size_t j = i;
while (j > left && a[j-1] > key) {
a[j] = a[j-1];
--j;
}
a[j] = key;
}
return;
}
// 随机 pivot
std::uniform_int_distribution<size_t> dist(left, right - 1);
size_t pivot_idx = dist(rng); // rng 是 thread_local std::mt19937
std::swap(a[pivot_idx], a[right - 1]);
// Lomuto partition（简单不易错）
int pivot = a[right - 1];
size_t i = left;
for (size_t j = left; j < right - 1; ++j) {
if (a[j] <= pivot) {
std::swap(a[i], a[j]);
++i;
}
}
std::swap(a[i], a[right - 1]);
// 尾递归优化：先处理小半边，大半边用循环模拟
if (i - left < right - i - 1) {
quick_sort(a, left, i);
left = i + 1; // 进入下一轮循环处理右半
} else {
quick_sort(a, i + 1, right);
right = i; // 进入下一轮循环处理左半
}}
用 std::nth_element 替代部分场景
如果你其实只需要「第 k 小的数」或「前 k 个最小元素」，根本不用完整排序。std::nth_element 平均 O(n)，内部也用类似快排的分区逻辑，但只保证第 k 位正确，左右不排序。它比完整 std::sort 快得多，且无栈溢出风险：
std::nth_element(v.begin(), v.begin() + k, v.end()); // v[k] 就是第 k+1 小
特别适合 top-K、中位数、分位数等场景。
真正难的不是写出快排，是判断该不该写、写到哪一层、以及什么时候该停手换标准库工具。边界检查、递归深度、pivot 随机性，三者漏一，生产环境就容易翻车。
立即学习“C++免费学习笔记（深入）”；
