快速排序（Quick Sort）

快速排序是一种分治算法。它通过选择一个“基准”元素（pivot），将数组分成两个子数组：左边所有元素 ≤ 基准，右边所有元素 ≥ 基准，然后递归地对两个子数组进行快速排序。

核心步骤（分治三部曲）：

分解（Partition）：选取基准，重新排列数组，使得左半 ≤ 基准 ≤ 右半，并返回基准的最终位置。
递归（Conquer）：对基准左边和右边的子数组递归进行快速排序。
合并（Combine）：由于是原地排序，无需合并步骤。

关键词：不稳定排序、原地排序、分治、平均 O(n log n)、最坏 O(n²)

算法步骤（升序为例）

假设要对数组 arr[l..r] 进行排序：

终止条件：l >= r，即子数组长度 ≤ 1，直接返回。
划分：调用 partition(arr, l, r)，将数组分成两部分，返回基准下标 pivotIndex。
递归左半：quickSort(arr, l, pivotIndex - 1)
递归右半：quickSort(arr, pivotIndex + 1, r)

划分方法（Partition）

有多种划分实现方式，最经典的是 Lomuto 划分 和 Hoare 划分。

Lomuto 划分（简单易懂）

思路：选择最后一个元素作为基准，用指针 i 标记小于基准的区域边界，遍历 j 从 l 到 r-1，若 arr[j] ≤ pivot，则交换 arr[i] 和 arr[j]，并 i++。最后交换 arr[i] 和 arr[r]（将基准放到正确位置）。

int partitionLomuto(int arr[], int l, int r) {
    int pivot = arr[r];   // 选择最后一个元素为基准
    int i = l;            // i 指向小于基准区域的下一个位置
    for (int j = l; j < r; ++j) {
        if (arr[j] <= pivot) {
            swap(arr[i], arr[j]);
            ++i;
        }
    }
    swap(arr[i], arr[r]); // 将基准放到正确位置
    return i;
}

特点：实现简单，但交换次数较多，且当数组已有序时分区极不平衡。

Hoare 划分（更高效）

思路：选择中间元素为基准，使用两个指针 i 和 j 分别从两端向中间移动，交换所有逆序对，最后返回分区点。这种方法交换次数更少，通常更快。

int partitionHoare(int arr[], int l, int r) {
    int pivot = arr[l + (r - l) / 2]; // 选中间元素避免极端情况
    int i = l - 1, j = r + 1;
    while (true) {
        do i++; while (arr[i] < pivot);
        do j--; while (arr[j] > pivot);
        if (i >= j) return j;
        swap(arr[i], arr[j]);
    }
}

注意：Hoare 返回的 j 是右半部分的起点，递归调用时为 quickSort(arr, l, j) 和 quickSort(arr, j+1, r)。

代码实现

经典递归快速排序（Lomuto 划分）

#include <iostream>
using namespace std;

void swap(int &a, int &b) {
    int t = a; a = b; b = t;
}

int partition(int arr[], int l, int r) {
    int pivot = arr[r];
    int i = l;
    for (int j = l; j < r; ++j) {
        if (arr[j] <= pivot) {
            swap(arr[i], arr[j]);
            ++i;
        }
    }
    swap(arr[i], arr[r]);
    return i;
}

void quickSort(int arr[], int l, int r) {
    if (l >= r) return;
    int p = partition(arr, l, r);
    quickSort(arr, l, p - 1);
    quickSort(arr, p + 1, r);
}

int main() {
    int arr[] = {5, 3, 8, 6, 2, 7, 1, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    quickSort(arr, 0, n - 1);
    for (int i = 0; i < n; ++i)
        cout << arr[i] << " ";
    return 0;
}

随机化快速排序（推荐竞赛使用）

为避免最坏情况，可以随机选择基准。

#include <cstdlib>
#include <ctime>

int randomPartition(int arr[], int l, int r) {
    int randomIndex = l + rand() % (r - l + 1);
    swap(arr[randomIndex], arr[r]); // 将随机基准换到末尾
    return partition(arr, l, r);    // 调用普通 Lomuto 划分
}

void quickSortRandom(int arr[], int l, int r) {
    if (l >= r) return;
    int p = randomPartition(arr, l, r);
    quickSortRandom(arr, l, p - 1);
    quickSortRandom(arr, p + 1, r);
}

三路快速排序（处理大量重复元素）

当数组有许多相等元素时，三路划分将等于基准的元素放在中间，避免重复比较。

void quickSort3Way(int arr[], int l, int r) {
    if (l >= r) return;
    int pivot = arr[l];
    int lt = l;     // arr[l+1..lt] < pivot
    int i = l + 1;  // 当前扫描位置
    int gt = r;     // arr[gt..r] > pivot
    while (i <= gt) {
        if (arr[i] < pivot) swap(arr[lt++], arr[i++]);
        else if (arr[i] > pivot) swap(arr[i], arr[gt--]);
        else i++;
    }
    // 递归处理 <pivot 和 >pivot 的部分
    quickSort3Way(arr, l, lt - 1);
    quickSort3Way(arr, gt + 1, r);
}

复杂度分析

复杂度	值	条件
时间复杂度（平均）	$O(n \log n)$	划分平衡时
时间复杂度（最坏）	$O(n^2)$	每次划分极度不平衡（如已有序且选择首尾为基准）
时间复杂度（最好）	$O(n \log n)$	每次划分都均衡
空间复杂度	$O(\log n)$	递归栈深度（最坏 $O(n)$ ）
稳定性	不稳定	因为交换可能打乱相等元素的相对顺序

递推公式（平均情况）： $T(n) = 2T(n/2) + O(n) → O(n \log n)$

最坏情况：当数组已经有序或逆序，且每次选最左或最右为基准，划分得到 $T(n) = T(n-1) + O(n) → O(n^2)$

快速排序的特点

优点

原地排序：不需要额外数组（递归栈除外），空间效率高。
平均性能最好：实际运行速度比归并排序、堆排序都快（常数因子小）。
缓存友好：顺序访问内存，局部性好。
可以优化：结合插入排序、随机化基准、三路划分等，适合工程应用。

缺点

不稳定：不能保证相等元素的原始顺序。
最坏情况差：但通过随机化或三数取中基本可以避免。
递归深度：最坏深度 $O(n)$，可改用迭代或尾递归优化。

优化技巧（竞赛常见）

随机化基准
pivot = arr[l + rand() % (r-l+1)] 几乎避免最坏情况。
三数取中
选择 arr[l]、arr[mid]、arr[r] 的中位数作为基准，减少极端概率。
小区间改用插入排序
当子数组长度小于某个阈值（如 10~20）时，改用插入排序，提升小规模数据效率。

   if (r - l + 1 <= 16) {
       insertionSort(arr, l, r);
       return;
   }

尾递归优化
先递归处理较小的子数组，再迭代处理较大的，减少栈深度。
三路快排（见上文）
处理大量重复元素时性能优异。

应用场景

通用排序：在内存中排序大量数据时首选。
求第 k 大/小的元素（快速选择）：基于 partition 的线性算法。
部分排序：如只关心前 k 个最小元素。
作为其他算法的基础：如快速排序的变体用于构造笛卡尔树等。

快速选择算法（求第 k 小）

int quickSelect(int arr[], int l, int r, int k) {
    if (l == r) return arr[l];
    int p = partition(arr, l, r);  // 返回基准下标
    if (k == p) return arr[p];
    else if (k < p) return quickSelect(arr, l, p - 1, k);
    else return quickSelect(arr, p + 1, r, k);
}
// 注意：k 是 0-based 下标，求第 k 小的元素

快速排序 vs 归并排序

特性	快速排序	归并排序
平均时间复杂度	$O(n \log n)$	$O(n \log n)$
最坏时间复杂度	$O(n^2)$ （可优化）	$O(n \log n)$
空间复杂度	$O(\log n)$ 栈	$O(n)$ 辅助数组
稳定性	不稳定	稳定
是否原地排序	是	否（通常）
适用场景	内存内通用排序，速度要求高	稳定性要求，外部排序，链表排序

竞赛建议：

一般情况下，直接用 std::sort（它是混合排序：快速排序+堆排序+插入排序）。
需要手写快排时，务必随机化基准，并使用三路划分处理重复元素。

常见考题变式

求数组的第 k 大元素：快速选择。
颜色分类（荷兰国旗问题）：三路快排变体。
使数组有序的最小交换次数：可以结合快速排序思想。
将奇数放在偶数前面：划分思想应用。
最接近中位数的 k 个数：快速选择找到中位数，再划分。