算法介绍：

    通过一趟排序将待排序记录分成独立的两部分，其中一部分记录的关键字小于或者等于另外一部分的关键字，
    然后分别对这两部分继续进行排序，从而达到整体有序。

基本原理与实现：

快速排序的工作原理是通过分治的方式来将一个数组排序。
快速排序实现的过程：

1. 将数列划分为两部分（要求保证相对大小关系）；
2. 递归到两个子序列中分别进行快速排序；
3. 不用合并，因为此时数列已经完全有序。

实现策略1：

    在待排序的数组a[0...n-1]中任选一个元素作为基准，通过一趟排序将数组划分为独立的两部分a[0...k-1]
    和a[k+1...n-1],使得a[0...k-1]的所有元素小于a[k]，a[k+1...n-1]的所有元素大于等于a[k],a[k]放在了
    其最终的位置上。然后分别对a[0..k-1]和a[k-1...n-1]重复上述过程，直至每一部分内只有一个元素或者空为止。

void quick_sort(int a[], int l, int r) {
    if(l >= r) return ;
    int x = a[l], i = l, j = r;
    while(i < j) {
        while(i < j && a[j] >= x) --j;
        a[i] = a[j];
        while(i < j && a[i] <= x) ++i;
        a[j] = a[i];    
    }
    a[i] = x;
    quick_sort(a, l, i - 1);
    quick_sort(a, i + 1, r);
}

实现策略2：

    在待排序的数组a[0...n-1]中任选一个元素作为基准，通过一趟排序将数组划分为独立的两部分a[0...k], a[k+1
    .. n-1],使得a[0...k-1]的所有元素小于等于该基准，a[k+1...n-1]的所有元素大于等于该基准,与策略1不同的是
    ，该基准元素在一趟排序过后其位置不一定在其最终位置。每趟排序结果如图所示：

void quick_sort(int a[], int l, int r) {
    if(l >= r) return ;
    int i = l - 1, j = r + 1, x = a[l + r >> 1];
    while(i < j) {
        do i++; while(a[i] < x);
        do j--; while(a[j] > x);
        if(i < j) swap(a[i], a[j]);
    }
    quick_sort(a, l, j);
    quick_sort(a, j + 1, r);
}

实现策略3（迭代实现快排）：

    递归转迭代的关键是找到方法保存本次运行的结果的状态以供下次迭代使用，以下代码是创建一个结构体数组保存
    每次迭代的指针，然后将策略2的递归实现转为迭代实现。

struct Point{
    int st, ed;
    Point(int s = 0, int e = 0) : st(s), ed(e) {}
};

void quick_sort(int a[], int l, int r) {
    if(l >= r) return ;
    int p = 0;
    Point point[r + 1];
    point[p++] = Point(l, r);
    while(p) {
        Point t = point[--p];
        if(t.st >= t.ed) continue;
        int x = a[t.st + t.ed >> 1];
        int i = t.st - 1, j = t.ed + 1;
        while(i < j) {
            do i++; while(a[i] < x);
            do j--; while(a[j] > x);
            if(i < j) swap(a[i], a[j]);
        }
        point[p++] = Point(t.st, j);
        point[p++] = Point(j + 1, t.ed);
    }
}

三路快排

    与原始的快速排序不同，三路快速排序在选取基准后，将待排数列划分为三部分：小于基准，等于基准，大于基准。
    这样做即实现了将与基准元素相等的元素聚集在分界元素周围这一效果。

void quick_sort(int a[], int l, int r) {
    if(l >= r) return ;
    int x = a[l + r >> 1];
    //i：等于x部分的第一个元素所在位置
    //j:也就是>x部分的第一个元素所在位置
    //k:当前操作的元素
    int i = l, j = r + 1, k = l;
    while(k < j){
        if(a[k] < x)
            swap(a[k++], a[i++]);
        else if(a[k] > x)
            swap(a[k], a[--j]);
        else 
            k++;
    }
    quick_sort(a, l, i - 1);
    quick_sort(a, j, r);
}

参考资料

https://oi-wiki.org/basic/quick-sort/
https://www.acwing.com/activity/content/code/content/39784/