快排递归实现的核心结构是什么
快排递归实现的关键不是写对 partition，而是控制好递归边界和子数组划分逻辑。很多初学者卡在无限递归或越界访问上，根本原因是没想清楚「左闭右开」还是「左闭右闭」的区间约定，且没处理好单元素或空数组的退出条件。
推荐统一用左闭右闭（l 和 r 都有效），退出条件必须是 l >= r，不能写成 l > r —— 否则当 l == r（单元素）时仍会继续递归，导致栈溢出。
-
partition返回的是基准值最终位置，左右子区间应为[l, pos-1]和[pos+1, r] - 递归调用前必须检查子区间有效性，比如
if (l - 避免在
partition中使用std::swap以外的复杂操作，尤其别在里面调用递归或分配内存
partition 函数最容易写错的三个地方
90% 的运行时错误（如 std::out_of_range 或无限循环）都出在 partition。它不只负责交换，更负责保证索引不越界、循环能终止、返回位置合法。
- 双指针从两端向中间走时，必须先移动再比较：比如
while (i ，漏掉 <code>i 判断会导致 <code>i越界 - 基准选
arr[r]时，swap(arr[i], arr[r])必须在循环结束后执行，且i此时指向第一个大于 pivot 的位置，所以返回i（不是i-1） - 如果用
arr[l]当 pivot，就得反向设计指针方向，否则逻辑错位；混用不同 pivot 策略但没改指针逻辑，必崩
std::sort 为什么比手写快排快
手写递归快排在小数组或已近序时性能反而差，而 std::sort 是混合排序（introsort）：小数组切到插入排序，深度过深切到堆排序，还做了分支预测优化。你写的纯递归版本没有这些兜底机制。
立即学习“C++免费学习笔记（深入）”；
- 对长度
- 最坏情况（如已排序数组）下，纯递归快排退化成 O(n²)，而
std::sort用深度计数器强制切换到堆排序 - 递归调用栈深度默认约 1000 层，对百万级数组极易触发
stack overflow，而std::sort内部用迭代模拟部分递归
要不要自己实现快排
除非练手、面试、嵌入式环境禁用 STL，否则真没必要。但练手时得盯住两个硬指标：是否通过所有边界测试（空数组、单元素、全相同、逆序），以及是否在 -O2 下不比 std::sort 慢太多。
- 测试用例至少包含：
std::vector<int>{}</int>、{42}、{3,3,3,3}、{5,4,3,2,1} - 别用
rand()做 pivot——它在某些平台低比特周期短，容易触发最坏路径；改用arr[l + (r-l)/2]或arr[r]更稳 - 如果函数要支持任意类型，模板参数必须带
Compare，且partition中所有比较都走它，否则无法适配自定义类型
递归深度和 pivot 选择策略，才是实际压测时最先暴露的问题，不是语法对不对。
