【模板】快速排序

题目链接：洛谷 P1177 【模板】快速排序

1960年由查尔斯·安东尼·理查德·霍尔（Charles Antony Richard Hoare，缩写为C. A. R. Hoare）提出。

如下图所示，快速排序的执行流程为：

① 从序列中选择一个轴点元素 pivot，假设每次选择最左边的元素为轴点元素。

② 利用 pivot 将序列分割成 2 个子序列：

• 将小于 pivot 的元素放在 pivot 前面（左侧）
• 将大于 pivot 的元素放在 pivot 后面（右侧）
• 等于 pivot 的元素放哪边都可以

③ 对子序列进行 ①、② 操作，直到不能再分割（子序列中只剩下 1 个元素）。

从上图中可以发现，快速排序的每一轮处理其实就是将这一轮的轴点元素归位，直到所有的数都归位为止，排序就结束了。也就是说，快速排序的本质就是逐渐将每一个元素都转换成轴点元素。

如果轴点左右元素数量比较均匀，即最好情况下 T ( n ) = 2 ∗ T ( n / 2 ) + O ( n ) T(n) = 2 ∗ T(n/2) + O(n) T(n)=2∗T(n/2)+O(n)，由 迭代和递归的时间复杂度分析 可知，时间复杂度为 O ( n log ⁡ n ) O(n \log{n}) O(nlogn)。

如果轴点左右元素数量极度不均匀，即最坏情况下 T ( n ) = T ( n − 1 ) + O ( n ) T(n) = T(n-1) + O(n) T(n)=T(n−1)+O(n)，由 迭代和递归的时间复杂度分析 可知，时间复杂度为 O ( n 2 ) O(n^2) O(n2)。

平均时间复杂度为 O ( n log ⁡ n ) O(n \log n) O(nlogn)。

由于递归调用的缘故，空间复杂度为 O ( log ⁡ n ) O(\log n) O(logn)。

快速排序属于不稳定排序。

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 100010;

int a[N];

void QuickSort(int left, int right)
{
    if (left >= right) return;
    
    int i = left, j = right;
    
    // 取中间的元素为轴点元素
    swap(a[left], a[left + right >> 1]);
    int pivot = a[left];
    
    while (i < j)
    {
        while (i < j && a[j] > pivot) j--;
        if (i < j) a[i++] = a[j];
        
        while (i < j && a[i] < pivot) i++;
        if (i < j) a[j--] = a[i];
    }
    
    // while循环退出时，i就是轴点位置，将轴点元素归位
    a[i] = pivot;
    
    QuickSort(left, i - 1); // 对轴点元素左边的元素[left,i-1]进行递归排序
    QuickSort(i + 1, right); // 对轴点元素右边的元素[i+1,right]进行递归排序
}

int main()
{
    int n;
    scanf("%d", &n);
    
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
    }
    
    QuickSort(0, n - 1);
    
    for (int i = 0; i < n; i++)
    {
        printf("%d%c", a[i], i == n - 1 ? '\n' : ' ');
    }
    
    return 0;
}

注意：

(1) 对于 洛谷 P1177 【模板】快速排序 来说，这道题的测试数据很严格，必须取中间的元素为轴点元素。

(2) 如果将下图中判断的位置分别改为 >= 和 <=，代码提交会超时。因为这样会导致轴点元素分割出来的子序列极度不均匀，从而出现最坏时间复杂度 O ( n 2 ) O(n^2) O(n2)。