17370845950

快速排序核心是分治：选基准将数组分为小于、等于、大于三部分，递归处理左右；需避免最坏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就切换），避免深层递归开销：

• if (right - left
• 递归调用前检查区间长度，空或单元素直接return
• 尾递归优化可手动转为while循环（只对较大子段递归，小子段立即处理）

完整可运行示例（简洁版）

以下代码含随机基准 + Lomuto分区 + 小数组优化：

void quick_sort(vector& 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);
}
int partition(vector& 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;
}

基本上就这些。分治不是玄学，是“先想清楚怎么拆，再放心交给自己去算”。写快排时多调试几个边界案例（全等、已序、逆序、两个数），比背模板管用得多。