一、核心思想：分治 + 分区
快速排序的流程：选一个 pivot（基准值），把小于 pivot 的放左边，大于的放右边。然后递归对左右两部分排序。
原始数组：[3, 7, 8, 5, 2, 1, 9, 5, 4]
选 pivot = 4（最后一个元素）
分区后：
小于 4 的部分 | pivot=4 | 大于等于 4 的部分
[3, 2, 1] | 4 | [7, 8, 5, 9, 5]
递归排序左边 [3, 2, 1] 和右边 [7, 8, 5, 9, 5]
二、Lomuto 分区（最简单，面试首选）
整体操作流程（Lomuto 分区）：
- 选基准：取最右侧元素
nums[right]作为 pivot。 - 双指针扫描：
i指向"小于区域的边界"，j从左到右扫描。 - 交换：如果
nums[j] < pivot，将它与nums[i]交换，i++（扩大小于区域）。 - 归位 pivot：扫描结束后，将 pivot（
nums[right]）交换到nums[i]位置。 - 返回 pivot 索引：此时
i就是 pivot 的正确位置。
整体操作流程（quickSort 递归）：
- 终止条件：如果
left >= right，区间为空或只有一个元素，直接返回。 - 分区：调用
partition得到 pivot 位置p。 - 递归左半：对
[left, p-1]排序。 - 递归右半：对
[p+1, right]排序。
int partition(vector<int>& nums, int left, int right) {
int pivot = nums[right]; // ① 选最右为基准值
int i = left; // ② i 指向小于区域的边界
for (int j = left; j < right; j++) { // ③ 从左到右扫描
if (nums[j] < pivot) { // ④ 发现小于 pivot 的元素
swap(nums[i], nums[j]); // ⑤ 交换到小于区域
i++; // ⑥ 扩大小于区域
}
}
swap(nums[i], nums[right]); // ⑦ 将 pivot 放到正确位置
return i; // ⑧ 返回 pivot 的最终索引
}
void quickSort(vector<int>& nums, int left, int right) {
if (left >= right) return; // ① 区间无元素或只有一个
int p = partition(nums, left, right); // ② 分区，p 是 pivot 位置
quickSort(nums, left, p - 1); // ③ 递归排序左半
quickSort(nums, p + 1, right); // ④ 递归排序右半
}
Lomuto 分区的执行过程（nums = [3, 7, 8, 5, 2, 1, 9, 5, 4], pivot=4）：
i=0, j=0: nums[0]=3 < 4 → swap(3,3), i=1
j=1: nums[1]=7 ≥ 4 → 不动
j=2: nums[2]=8 ≥ 4 → 不动
j=3: nums[3]=5 ≥ 4 → 不动
j=4: nums[4]=2 < 4 → swap(7,2), i=2 → [3,2,8,5,7,1,9,5,4]
j=5: nums[5]=1 < 4 → swap(8,1), i=3 → [3,2,1,5,7,8,9,5,4]
j=6: nums[6]=9 ≥ 4 → 不动
j=7: nums[7]=5 ≥ 4 → 不动
最后 swap(nums[3]=5, nums[8]=4) → [3,2,1,4,7,8,9,5,5]
返回 i=3
时间复杂度：
- 平均：$O(N \log N)$
- 最坏（已经有序，每次选到最大/最小）：$O(N^2)$
- 空间复杂度：$O(\log N)$（递归栈）
三、快排为什么在实际中比归并排序快？
缓存局部性：快排的分区操作在原地进行，数据访问是顺序的——从 left 扫描到 right。归并排序需要额外的 $O(N)$ 空间来合并，合并时读写两个数组之间的数据，缓存行为更差。
快排分区时的内存访问模式：
[3, 7, 8, 5, 2, 1, 9, 5, 4]
↑扫描方向→ ←pivot
顺序访问！CPU 预取器能提前加载
归并排序合并时的内存访问模式：
左半 [1, 2, 3, 5, 7] 右半 [4, 5, 8, 9]
↘ 交替读取两个数组 ↙
缓存行在两个数组之间跳动，预取效果差
实测（排序 1000 万随机 int）：
- 快排：~700ms
- 归并排序：~950ms（慢 35%）
四、面试追问 Q&A
Q1：如何避免快排退化到 $O(N^2)$？ A：三种策略：
- 随机选 pivot：
swap(nums[right], nums[left + rand() % (right-left+1)])，让最坏情况的概率趋近于 0。 - 三数取中：选 left、mid、right 的中位数做 pivot。
- 切换到插入排序：当子数组小于某个阈值（如 16）时，改用插入排序。这是
std::sort的做法。
Q2：std::sort 为什么不直接用快排？
A：std::sort 是内省排序（IntroSort）——开始用快排，如果递归深度超过 $2\log N$（说明遇到了接近最坏情况），切换到堆排序保证 $O(N \log N)$。这是快排+堆排的混合体。
Q3：Lomuto 和 Hoare 分区有什么区别？ A：
- Lomuto：简单易懂（面试首选），但当数组中重复元素很多时效率略低。
- Hoare：从两端向中间扫描，交换次数更少，实际更快。但实现稍复杂。
- 两者时间复杂度一样，常数 Hoare 略优。