快速排序（c++)

快速排序是目前应用最广泛的排序算法之一，"它的基本思想与归并排序类似，也是基于分治的。每次从待排序区间选取一个元素(我们在后面的课程中都是选取第一个)作为基准，所有比基准小的元素都在基准的左边，而所有比基准大的元素都在基准的右边。之后分别对基准记录的左边和右边两个区间递归地进行快速排序

int a[100005];
void quick_sort(int l, int r) {
    if(l >= r){
        return;
    }
    int p1 = l, p2 = r;
    int pivot = l;
    while(p1 < p2){
        while(a[p2] >= a[pivot] && pivot < p2){
            p2--;
        }
        if(pivot < p2){
            swap(a[pivot], a[p2]);
            pivot = p2;
        }
        while(a[p1] <= a[pivot] && pivot > p1){
            p1++;
        }
        if(pivot > p1){
            swap(a[pivot], a[p1]);
            pivot = p1;
        }
    }
    quick_sort(l, pivot - 1);
    quick_sort(pivot + 1, r);
}

上述代码中，如果当前区间只有一个元素或为空，就直接返回。
p1 和 p2 是两个用于扫描的指针，分别从左往右和从右往左扫，直到他们相遇为止。每一轮可以看作两步:
    1.自右向左扫找到右边第一个小于基准的位置后交换；
    2.自左向右扫找到左边第一个大于基准的位置后交换；
这样一轮结束后，基准值被落在了正确的位置，之后递归地对左边和右边的元素做快速排序即可 

可以证明快速排序的平均时间复杂度为 (n log n)，最坏情况下时间复杂度为 (n ^ 2)，可以通过随机选择基准记录来尽可能避免最坏情况的出现。

快速排序是不稳定的排序算法。

快速选择 

快速选择是基于快速排序算法查找第 k 小(大)数的问题
原理: 每一轮快速排序的过程中：
  左边所有数<基数；
  右边所有数 >= 基数；
那么在每一轮排序的过程中基数的位置就是排序后该数的位置

如果我们现在想要求解第 k 小的数，每次让 k 和排序后基数的位置 id 进行比较，若
  k = id，找到第k 小的数；
  k < id，在左区间内递归求解；
  k > id，在右区间内递归求解；
例如k = 6时: 

因为快速选择是基于快速排序算法，平均时间复杂度为 O(n)，最坏情况下时间复杂度为 (n ^ 2)。  

代码展示

#include <algorithm>
#include <iostream>
using namespace std;
int a[100005];
void quick_sort(int l, int r) {
    if(l >= r){
        return;
    }
    int p1 = l, p2 = r;
    int pivot = l;
    while(p1 < p2){
        while(a[p2] >= a[pivot] && pivot < p2){
            p2--;
        }
        if(pivot < p2){
            swap(a[pivot], a[p2]);
            pivot = p2;
        }
        while(a[p1] <= a[pivot] && pivot > p1){
            p1++;
        }
        if(pivot > p1){
            swap(a[pivot], a[p1]);
            pivot = p1;
        }
    }
    quick_sort(l, pivot - 1);
    quick_sort(pivot + 1, r);
}
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    quick_sort(0, n - 1);
    for (int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }
    return 0;
}