std::sort 不是手写快排的替代，因其采用 introsort 混合实现且不暴露分区逻辑；手写快排适用于理解本质、调试边界或禁用 STL 场景；partition 函数需确保左右指针不越界，常见错误是 l < r 判定缺失或交换前未校验索引。
为什么 std::sort 不是手写快排的替代参考
标准库的 std::sort 内部通常用 introsort（快排 + 堆排 + 插入排序混合），不是纯快排，且不暴露分区逻辑。想理解快排本质、调试分区边界、或在嵌入式/教学场景禁用 STL 时，必须手写递归分区版本。
partition 函数怎么写才不越界
常见错误是 l 判定后仍让指针多走一步，导致访问 <code>arr[r+1] 或 arr[l-1]。正确做法是双指针在循环内严格约束索引范围，并在交换前二次检查：
int partition(std::vector<int>& arr, int l, int r) {
int pivot = arr[r];
int i = l - 1;
for (int j = l; j < r; ++j) {
if (arr[j] <= pivot) {
++i;
std::swap(arr[i], arr[j]);
}
}
std::swap(arr[i + 1], arr[r]);
return i + 1;
}-
l和r必须是有效下标，调用前确保l - 主循环用
j ，不是 <code>j ，避免拿 <code>arr[r]和自己比 - 返回的是新 pivot 位置，后续递归区间为
[l, pos-1]和[pos+1, r]
递归调用时栈溢出和性能陷阱
最坏情况（已排序数组）下递归深度 O(n)，极易触发栈溢出；同时小数组线性扫描比递归更快。优化必须做两件事：
- 对小规模子数组（如
length ）切换为 <code>std::insertion_sort或手写插入排序 - 递归前先处理较小区间，再用尾递归优化大区间（即先递归左半边，右半边用 while 循环代替）
- 随机化 pivot：
std::swap(arr[r], arr[l + rand() % (r - l + 1)])，避免退化
迭代版快排真的比递归快吗
迭代实现用显式栈模拟递归，能彻底消除栈溢出风险，但实际性能不一定更高——现代 CPU 对递归调用的预测和缓存友好度很好，而手动栈要额外管理 vector 或 array，还可能因内存分配拖慢。除非明确遇到栈深问题，否则优先优化递归版本，而不是盲目转迭代。
立即学习“C++免费学习笔记（深入）”；
真正影响性能的关键是 pivot 选择、小数组阈值、内存局部性（比如用 std::span 避免 vector 迭代器开销），而不是“递归 or 迭代”这个表层选择。
