partition函数需确保i、j不越界：先i++再比较，先j--再比较，循环条件为i
partition 函数怎么写才不越界
快排核心是 partition，考研常考边界处理。常见错误是用 left 和 right 做下标时，while (arr[i] 没加 i 判断，导致访问越界。正确写法必须双检查：内层循环都要带下标范围约束。
推荐使用「挖坑填数」或「双指针交换」两种稳定写法。例如双指针：
int partition(vector& arr, int left, int right) { int pivot = arr[left]; int i = left, j = right; while (i < j) { while (i < j && arr[j] >= pivot) j--; if (i < j) arr[i++] = arr[j]; while (i < j && arr[i] <= pivot) i++; if (i < j) arr[j--] = arr[i]; } arr[i] = pivot; return i; }
-
arr[j] >= pivot和arr[i] 中的等号决定是否稳定（考研不要求稳定，但等号影响重复元素分布） - 每次
while内部都必须先判i ，否则j--后可能j == left - 1 - 返回值是 pivot 最终位置，用于后续递归切分
递归调用时左右区间怎么取
递归调用 quickSort(arr, left, pos-1) 和 quickSort(arr, pos+1, right) 是标准写法，但容易错在边界重叠或漏掉单元素。关键点是：pivot 所在位置 pos 已经排好，不再参与后续排序。
- 左半部分是
[left, pos-1]，不是[left, pos]—— 否则会重复排 pivot - 右半部分是
[pos+1, right]，不是[pos, right] - 递归终止条件必须是
left >= right，不能只写left == right，否则长度为 0 的子数组（如left=3, right=2）会无限递归
为什么考试要手动实现而不是用 sort()
考研算法题明确要求「手写快排」，本质是考察对分治结构、原地排序、递归边界、最坏复杂度的理解。用 std::sort 直接得 0 分——它底层是 introsort（快排+堆排+插入），不体现分治逻辑。
立即学习“C++免费学习笔记（深入）”；
- 题目中若出现「不允许使用 STL 算法」或「要求时间复杂度平均 O(n log n)，空间复杂度 O(log n)」，就是在提示你写递归快排并控制栈深度
- 如果要求「非递归版本」，需用显式栈模拟，但考研极少考；重点还是递归结构是否清晰
- 实际笔试中，哪怕
partition写错一两个比较符号，只要主框架（分治+递归调用）正确，也能拿大部分步骤分
随机化 pivot 能不能加分
可以，而且强烈建议加。原版快排最坏 O(n²)，比如已排序数组做输入时退化成链表式递归。考研代码若只写 pivot = arr[left]，遇到极端测试用例会扣分。
- 加一句
swap(arr[left], arr[left + rand() % (right - left + 1)]);就能避免最坏情况 - 注意：C++11 后推荐用
rand()，只需加srand(time(0))在 main 开头（如果完整程序） - 不过，如果题目明确说「以首元素为基准」，那就不能改——务必看清题干要求
递归深度和 pivot 选择是快排最容易被忽略的两个得分点，尤其后者，很多同学背熟模板却栽在没随机化上。
