快速排序核心是分治递归：选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。
常见崩溃点：storeIndex 初始化为 left 而非 left - 1，导致第一个小元素被跳过；或遍历时用了 i 却忘了 pivot 在 <code>right，造成重复比较。
C++ Code Review Master
下载
组合式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 <h3>递归深度太大导致栈溢出怎么办</h3>
<p>最坏情况（已排序数组+每次都选端点作 pivot）下递归深度是 O(n)，容易触发 stack overflow。这不是算法写错了，而是工程现实问题。</p>
<p>解决方式不是换语言，而是加两个小优化：</p>
<ul>
<li>每次递归前，先处理较短的子区间，再用尾递归技巧处理较长的——即把第二次递归调用改成 while 循环，避免新增栈帧</li>
<li>当子数组长度小于某个阈值（如 10），改用插入排序。<code>std::sort</code> 就是这么干的</li>
<li>随机化 pivot：在 partition 前 <code>swap(arr[right], arr[left + rand() % (right - left + 1)])</code>，大幅降低退化概率</li>
</ul>
<h3>C++里要不要用 std::sort 替代手写 quickSort</h3>
<p>绝大多数场景应该直接用 <code>std::sort</code>。它不是纯 quickSort，而是 introsort（快排 + 堆排 + 插入排序混合），既保证平均 O(n log n)，又规避最坏 O(n²)，还做了缓存友好优化。</p>
<p>手写 quickSort 的合理理由只剩两个：教学理解分治思想，或嵌入式等极端受限环境无法用 STL。但即使教学，也建议对比测试：用 <code>std::sort</code> 和自己写的版本对 10⁵ 随机整数排序，你会发现性能差距常在 2–5 倍——不是因为你写得差，而是 <code>std::sort</code> 内联了分支预测、用 SIMD 做了小数组预处理。</p>
<p>真正容易被忽略的一点：<code>std::sort</code> 要求迭代器支持随机访问，<code>std::list</code> 就不能用；这时如果硬要“快排风格”，得换成基于链表的 partition，代价是失去 cache 局部性，实际可能比 <code>std::list::sort</code> 还慢。</p></int>C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
