快速排序

快排思想——分治

1.确定分界点

常用的方式有：q[l] 、q[(l + r) / 2]，q[r]

2.调整区间(难点)

假设确定好的分界点的值是x则调整后的左区间所有元素均 <= x,右区间的所有值均 >= x

Q：如何优雅的将其分成两个区间？

小k：简单，再新建两个临时数组tmp1[],tmp2[],小于基准点的放入第一个，大于基准点的放入第二个，最后再都放入原数组。(暴力的)

这种做法是典型的以空间换时间，如果不太记得优雅的方法的界限划分时倒也不失为一种方法

3.递归处理左右两端

快排模板

优雅的

void quick_sort(int q[], int l, int r){
    if(l >= r) return;//终止条件
    int x = q[l + r >> 1];//第一步，确定分界点
    int i = l - 1, j = r + 1;//注意这里的取值，因为下面使用的是do-while所以需要往两边扩一下
    while(i < j){//第二步，调整左右区间
        do i ++ ; while(q[i] > x);
           do j -- ; while(q[j] < x); //注意此处不能有等号，不然可能会死循环
        if(i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j), qucik_sort(q, j + 1, r);//第三步，递归处理左右两端；注意：这里的分界区间，天坑！！(都是泪)，和以首个元素为基准点的划分不一样，且以中间元素为基准点的划分每一次不会确定一个点的最终位置
}