快速排序

基本思想

快速排序，简称快排。升序排序是通过选定一个基准点，这个基准点可以选最中间元素或者是第一个元素，将比这个基准点小的元素放在左边，大的元素放在右边，实现基准点左边的元素小于等于基准点的值，右边的元素大于等于基准点的值（只是将元素放在两边，并不是有序的），然后分别递归左边和右边逐步实现排序。

C++代码

void quick_sort(int left, int right, int a[]) {
    //以第一个元素为基准点
    int t = a[left], l = left, r = right;
    while (l < r) {
        //从右向左遍历直到遇到一个元素小于基准点
        while (l < r && a[r] >= t) r--;
        //将找到的元素放到左边
        if (l < r) a[l++] = a[r];
        //从左向右遍历直到遇到一个元素大于基准点
        while (l < r && a[l] < t) l++;
        //将找到的元素放到右边
        if (l < r) a[r--] = a[l];
    }
    a[l] = t;//此时l == r, 即l对应的元素为基准点所在的位置 
    if (left < l - 1)//递归遍历左半边
        quick_sort(left, l - 1, a);
    if (right > l + 1)//递归遍历右半边
        quick_sort(l + 1, right, a);
}