快速排序是 OI 中常用的算法。这篇题解/笔记将会详细地讲解快速排序的原理、实现过程，也会拓展 STL sort 函数的使用和快排复杂度及其证明。

快速排序的原理

image.png

快速排序如何用 C++ 实现？ 我们以洛谷 P1177 【模板】排序为例来讲解这一算法的实现过程。

普通自定义函数 首先，我们看完如上所示的实现方法与过程后，可以发现：实际上每一次的排序之后都会通过调用本身来继续排序，这明显就是递归的精髓。

确实，递归是快速排序的主要思想，通过递归，我们将一个完整的序列经过不断的分解来变成很多个小序列，直到只有一个或没有数为止。这种排序就是在不断的递归和分解当中来慢慢实现与完成排序。

这里，我们提供了这个函数的参考代码：

#include <bits/stdc++.h>
using namespace std;
const int LenN = 100005;
int arr[LenN];
int b[LenN],c[LenN],d[LenN];
// 注：四个数组的下标均从 0 开始。
// 产生随机数
int randint(int l,int r){
    return rand() % (r-l +1) + l;
}
// l 为左端点，r 为右端点
void quickSort(int l,int r){
    if(l >= r){
         //长度为 0，返回
         return;
    }
    // 给大家讲解一下为什么此时可以不用判长度为 1 的序列：
    // 因为序列中的这个数在添加的过程中会自动被分到 c 数组中去，而 c 在之后是不用排序的，
    // 相当于什么都没做，当然也可以在这里判一下长度为 1 的情况，直接 return 就可以了

    // 随机选择一个数，并定义三个作为下标的变量来记录长度、存放数据
    int num = randint(l,r);
    int lenb = 0,lenc=0,lend=0;
    for(int i = l; i<= r; i++){
        // 将 arr 中的数分别分到 b, c, d（如上所述）
        if(arr[i] < arr[num]){
            b[lenb++] = arr[i];
        }
        else if(arr[i] > arr[num]){
            d[lend++] = arr[i];
        }else{
            c[lenc++] = arr[i];
        }
    }    
    for(int i = 0;i < lenb;i++){ // 将 b, c, d 中的数重新放回 arr
        arr[i + l] = b[i];
    }
    for(int i = 0;i < lenc;i++){
        arr[i + lenb + l] = c[i];
    }
    for(int i = 0;i < lend;i++){
        arr[i + lenb + lenc + l] = d[i];
    }
    quickSort(l, l + lenb - 1); // 继续排序原来的 b 和 d
    quickSort(l + lenb + lenc, r);
}



int main(){
    int n;
    cin >> n;
    for(int i= 0;i<n; i++){
        cin >> arr[i];
    }
    quickSort(0,n-1);
    for(int i= 0;i<n; i++){
        cout <<  arr[i] << " ";
    }

    return 0;
}

拓展：STL sort 函数的使用

除了如上的快排模板外，我们还可以使用 C++ algorithm 头文件中的 sort 函数来直接完成排序，时间复杂度均为 O(nlogn)。其使用方法如下：

我们设我们排序的数组为 arr，排序区间为[l,r) ，且从小到大排序。则调用方法为：

sort(a + l, a + r);

注意，如果你想使用这个函数，你应该在头文件中加上 #include <algorithm> 或者 #include <bits/stdc++.h>（万能头文件）。

如果我们不想从小到大排序，而是想从大到小排序呢？那么我们就应该写一个比较函数（一般命名为 cmp）来改变排序方法。

例如我们想要把一个类型为 int 的数组从大到小排序，我们应该这么定义这个比较函数：

bool cmp(int a, int b){
	return a > b;
}

我们只需要定义两个与数组类型相同的变量作为参数，再返回两个数字的比较就可以了。

如果是从小到大排序，就用小于号连接两数；如果是从大到小排序，就用大于号连接两数，简记为：符号开口就代表大的在哪（大于号代表从大到小，小于号代表从小到大）。

写完这个函数，我们只需要在调用 sort 函数时在第三个参数写上函数名（例如 sort(arr + l, arr + r, cmp);）就可以了。

同样，结构体也可以用它排序。

例如我们定义一个结构体：

struct node{
	int x, y;
}c[1000];

此时，我们想这样对 c 排序：x 更大的在前，如果 x 相同则 y 更大的在前。

此时，我们可以这样写比较函数：

bool cmp(node a, node b){
	if(a.x != b.x){ // 如果两个 x 不等则以 x 的大小排序
		return a.x > b.x;
	}
	return a.y > b.y; // 否则以 y 的大小排序
}

快速排序的复杂度

image.png