std::sort不是手写快排的替代品，因其不暴露分区逻辑、无法自定义比较粒度，且无法控制pivot选择、递归深度等细节；手写快排需注意边界越界和死循环问题。
为什么 std::sort 不是手写快排的替代品
标准库的 std::sort 内部通常用 introsort（快排 + 堆排 + 插入排序混合），它不暴露分区逻辑，也没法自定义比较粒度（比如按结构体某个字段、或带状态的 lambda）。真要控制 pivot 选择、递归深度、尾递归优化，或者教学/面试场景下必须手写，就得自己实现。
基础版快排怎么写才不出错
常见错误是边界越界和死循环——尤其在 while (arr[i] 这类判断里漏掉 <code>i 检查。正确写法必须双指针收敛且保证 <code>i 和 j 不交叉：
- 选 pivot 推荐用
arr[(left + right) / 2]或随机索引，避免已排序数组退化到 O(n²) - 内层
while循环必须同时检查i 和值条件，例如：<code>while (i - 交换后要执行
i++和j--，否则可能卡在相等元素上无限循环 - 递归调用时，左右区间为
[left, j]和[i, right]，不是[left, i-1]和[i+1, right]（后者会漏掉i == j时的元素）
void quickSort(vector<int>& arr, int left, int right) {
if (left >= right) return;
int pivot = arr[(left + right) / 2];
int i = left, j = right;
while (i <= j) {
while (i <= j && arr[i] < pivot) i++;
while (i <= j && arr[j] > pivot) j--;
if (i <= j) {
swap(arr[i], arr[j]);
i++; j--;
}
}
quickSort(arr, left, j);
quickSort(arr, i, right);
}
如何避免栈溢出和提升性能
最坏情况下递归深度 O(n)，容易爆栈；小数组线性扫描比递归快。实用改进点很明确：
- 对长度
的子数组改用 <code>insertion_sort，直接写个内联循环就行 - 递归前先处理较小区间（尾递归优化），比如总是先递归左半边，右半边用循环重进，能压平一半栈帧
- 不用
rand() % (right - left + 1)做随机 pivot——rand()周期短且低比特质量差，改用std::uniform_int_distribution或简单异或时间戳
迭代版快排的关键控制点
用栈模拟递归，核心是「压栈顺序」和「区间表示」。容易错在：压入的区间边界没更新、重复压入、或忘记弹栈后继续处理：
立即学习“C++免费学习笔记（深入）”；
- 栈里存
pair<int int></int>表示[l, r]，初始压入{0, n-1} - 每次弹出一个区间，做完 partition 后，只把非空子区间压栈（即
if (l ） - 不要在 partition 过程中修改原栈顶数据，所有边界计算基于当前弹出的
l和r
迭代写法没有函数调用开销，但代码变长、可读性下降；除非明确受栈空间限制（如嵌入式环境），否则优先用带优化的递归版。
真正难的不是写出能跑的版本，而是想清楚 pivot 怎么选才不容易被构造数据打穿，以及等值元素多时要不要三路划分——那已经不是“快排实现”，而是工程权衡了。
