快速排序核心是分治递归：选pivot划分数组为小于、等于、大于三段，仅递归处理左右两段；关键注意闭区间[left, right]边界和partition后正确传入pivotIndex±1。
快速排序的核心逻辑是分治递归
快速排序不是靠内置函数或库调用实现的，它依赖手动划分（partition）和递归收缩区间。关键在于选一个基准值（pivot），把数组分成三部分：小于 pivot 的左段、等于 pivot 的中段、大于 pivot 的右段，然后只对左右两段递归处理。
实际编码时最容易出错的是边界条件——比如 left >= right 时没及时 return，或者 partition 后递归调用时传入了错误的下标范围，导致无限递归或越界访问。
- 推荐始终使用闭区间
[left, right]语义，避免混淆开闭边界 - 每次 partition 返回的是 pivot 最终落点的索引，递归调用应为
quickSort(arr, left, pivotIndex - 1)和quickSort(arr, pivotIndex + 1, right) - 不要在 partition 内部做 swap(arr[i], arr[j]) 时不检查
i ，否则可能原地交换两次变回原样
partition 函数怎么写才稳定不崩
最常用的是“挖坑填数”或“双指针”法。C++ 中推荐用双指针（Lomuto 或 Hoare 版本），其中 Hoare 更高效但初学者易写错循环终止条件；Lomuto 更直观，适合调试。
以 Lomuto 为例：取最后一个元素为 pivot，维护一个 storeIndex 指向已处理中小于等于 pivot 的区域右边界，遍历过程中遇到小元素就 swap 到 storeIndex 并自增。最后 swap storeIndex 和末尾 pivot。
立即学习“C++免费学习笔记（深入）”；
常见崩溃点：storeIndex 初始化为 left 而非 left - 1，导致第一个小元素被跳过；或遍历时用了 i 却忘了 pivot 在 <code>right，造成重复比较。
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
int partition(vector<int>& arr, int left, int right) {
int pivot = arr[right];
int storeIndex = left;
for (int i = left; i < right; i++) {
if (arr[i] <= pivot) {
swap(arr[i], arr[storeIndex]);
storeIndex++;
}
}
swap(arr[storeIndex], arr[right]);
return storeIndex;
}递归深度太大导致栈溢出怎么办
最坏情况（已排序数组+每次都选端点作 pivot）下递归深度是 O(n)，容易触发 stack overflow。这不是算法写错了，而是工程现实问题。
解决方式不是换语言，而是加两个小优化：
- 每次递归前，先处理较短的子区间，再用尾递归技巧处理较长的——即把第二次递归调用改成 while 循环，避免新增栈帧
- 当子数组长度小于某个阈值（如 10），改用插入排序。
std::sort就是这么干的 - 随机化 pivot：在 partition 前
swap(arr[right], arr[left + rand() % (right - left + 1)])，大幅降低退化概率
C++里要不要用 std::sort 替代手写 quickSort
绝大多数场景应该直接用 std::sort。它不是纯 quickSort，而是 introsort（快排 + 堆排 + 插入排序混合），既保证平均 O(n log n)，又规避最坏 O(n²)，还做了缓存友好优化。
手写 quickSort 的合理理由只剩两个：教学理解分治思想，或嵌入式等极端受限环境无法用 STL。但即使教学，也建议对比测试：用 std::sort 和自己写的版本对 10⁵ 随机整数排序，你会发现性能差距常在 2–5 倍——不是因为你写得差，而是 std::sort 内联了分支预测、用 SIMD 做了小数组预处理。
真正容易被忽略的一点：std::sort 要求迭代器支持随机访问，std::list 就不能用；这时如果硬要“快排风格”，得换成基于链表的 partition，代价是失去 cache 局部性，实际可能比 std::list::sort 还慢。
