快速排序核心是分治：选基准将数组分为小于、等于、大于三部分，再递归处理前后两部分；C++实现需注意边界控制、原地排序、三路优化及基准随机化等细节。
快速排序的核心是“分治”：选一个基准元素，把数组分成三部分——小于基准的、等于基准的、大于基准的，再递归处理前后两部分。C++实现时要注意边界控制和原地排序优化，避免额外空间开销。
基础版本：双指针分区（Lomuto分区方案）
这是最易理解的写法，用一个基准值（通常取末尾元素），维护一个慢指针 i 指向已处理中小于等于基准的区域右边界，快指针 j 遍历整个待排段。
关键步骤：
- 将基准元素（如 arr[r]）暂存，最后放回正确位置
- 遍历 i 从 l 到 r−1，若 arr[i] ≤ pivot，则与 arr[++j] 交换
- 循环结束后，把基准换到 j+1 位置，该位置就是它的最终索引
优化版本：三路快排（处理重复元素）
当数组中存在大量重复值时，标准快排可能退化为 O(n²)。三路快排把区间划分为 、== pivot、> pivot 三段，跳过所有等于基准的元素，大幅提升稳定性。
立即学习“C++免费学习笔记（深入）”；
实现要点：
- 用两个指针 lt（less than）和 gt（greater than），初始分别指向 l 和 r
- 用游标 i 从左往右扫描：
– 若 arr[i] ，交换 arr[i] 与 arr[++lt]；
– 若 arr[i] > pivot，交换 arr[i] 与 arr[--gt]，且 i 不增（因右边换来的数未检查）；
– 若相等，i++ 跳过
实用建议：避免常见陷阱
写快排容易出错的地方集中在递归边界和分区逻辑上：
- 递归调用时，左右子区间必须严格不重叠，比如分区后基准在 pos，则递归范围应为 [l, pos−1] 和 [pos+1, r]，不能写成 [l, pos]
- 小数组改用插入排序（例如长度 ≤10），减少递归开销
- 基准选取建议随机化：用 swap(arr[l], arr[l + rand() % (r−l+1)]) 防止有序数组最坏情况
- C++ 中注意使用引用传参（vector
& ）避免拷贝，提升效率
快排不是黑盒，理解分区过程比背代码更重要。动手写一遍 Lomuto 版本，再改成三路，你会明显感受到“划分”这个动作如何驱动整个排序流程。不复杂但容易忽略细节。
