快速排序核心是分治：选基准将数组分为小于、等于、大于三部分，递归处理左右；需避免最坏O(n²)，推荐随机选或三数取中选基准，并用Lomuto/Hoare双指针原地分区。
快速排序用C++实现，核心是分治：选一个基准（pivot），把数组分成三部分——小于、等于、大于基准的元素，再递归处理左右两部分。关键不在“快”，而在“分得清、治得稳”。
选好基准，别硬挑第一个
基准选得太偏（比如总选首尾），最坏情况会退化成O(n²)。实际中常用三种策略：
- 随机选：用rand() % (right - left + 1) + left取下标，再和末尾交换
- 三数取中：取首、中、尾三个数的中位数作基准，抗有序/逆序数据效果好
- 避免重复拷贝：直接在原数组上分区，不用额外容器存“等于”部分
双指针分区，原地完成
推荐Lomuto或Hoare分区方案。Lomuto更易懂，用一个游标i标记“
- 遍历j从left到right−1，遇到≤pivot的数，就swap(arr[++i], arr[j])
- 最后swap(arr[i+1], arr[right])，把pivot放到正确位置
- 返回i+1，即pivot最终下标，左右子数组就是[left, i]和[i+2, right]
递归控制，别忘剪枝
小数组用插入排序更高效（一般n ≤ 10就切换），避免深层递归开销：
立即学习“C++免费学习笔记（深入）”；
- if (right - left
- 递归调用前检查区间长度，空或单元素直接return
- 尾递归优化可手动转为while循环（只对较大子段递归，小子段立即处理）
完整可运行示例（简洁版）
以下代码含随机基准 + Lomuto分区 + 小数组优化：
void quick_sort(vector<int>& arr, int left = 0, int right = -1) {
if (right == -1) right = arr.size() - 1;
if (left >= right) return;
if (right - left <= 10) {
insertion_sort(arr, left, right);
return;
}
// 随机选基准并换到末尾
int rnd = left + rand() % (right - left + 1);
swap(arr[rnd], arr[right]);
int pivot_idx = partition(arr, left, right);
quick_sort(arr, left, pivot_idx - 1);
quick_sort(arr, pivot_idx + 1, right);
}
<p>int partition(vector<int>& arr, int left, int right) {
int pivot = arr[right], i = left - 1;
for (int j = left; j < right; ++j) {
if (arr[j] <= pivot) swap(arr[++i], arr[j]);
}
swap(arr[i + 1], arr[right]);
return i + 1;
}
基本上就这些。分治不是玄学，是“先想清楚怎么拆，再放心交给自己去算”。写快排时多调试几个边界案例（全等、已序、逆序、两个数），比背模板管用得多。
