快速排序

快速排序的思路：

随机选中序列中的一个元素，记为 x ，以此作为分界线
进行排序，排序后要满足的结果是：在 x 左边的元素全部小于等于 x，在 x 右边的元素全部大于等于 x
递归地对左右两边进行快速排序

这个思路的关键在于第二步：将比 x 小的元素全部放到左边，将比 x 大的数全部放到右边。这里采用双指针来完成这一步。

这个时间复杂度取决于所选取的 x 位于有序序列的什么位置

假设每一次选取的 x 都是位于有序序列的边缘，那么时间复杂度是 $O(n)$
假设每一次选取的 x 是有序序列的中点，那么时间复杂度为 $O(log_2n)$

题目链接

//传入要排序的数组 q ,数组的最左边 l ,数组的最右边 r
void quick_sort(int q[], int l, int r){
    //确定分界点,取中间的点的值
    int x = q[(l+r)>>1];
    int i = l-1, j = r+1;
    
    //数组没有元素的时候，不用排序
    if(l >= r) return;
    //数组存在元素时,划分左右区域
    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);
    quick_sort(q,j+1,r);
}

注意点1：代码中的 i++ 和 j-- 一定是在与 x 比较前执行的

举个简单的反例：1 2 2 2 3
那么此时的 x = 2
第一轮循环： i = 1， j = 3，然后交换 q[i] 和 q[j]
第二轮循环： i = 1， j = 3，然后交换 q[i] 和 q[j]
第三轮循环......

从上面的例子可以看出来，由于 q[i] = q[j] = 2，当我们先进行判断后移动的时候，并不会发生移动，会陷入死循环当中。

注意点2： i 与 j 停止移动的时候，j = i - 1 或者 j = i

证明：两者停止移动的时候，只有两种情况

i 向右移动直至越过 j，此时 q[j] >= x，因此 i = j
j 向左移动直至越过 i，此时 q[i] >= x，并且q[i - 1] <= x，因此 j = i - 1 或 j = i

注意点3：边界条件

这个边界条件指的是当只有两个数的时候，根据以下两个原因：

注意点2：i 与 j 停止移动的时候，j = i - 1 或者 j = i
while中的判断条件都是 < 或者 >，没有 <= 或者 >=

我们可以推断出:

若是 x = q[(l + r) >> 1] ，也就是取下边界，最终一定是 j = 0, i = 0 或 1
若是 x = q[(l + r + 1) >> 1]，也就是取上边界，最终一定是 i = 1, j = 0 或 1

针对第一条结论，若是下一次的快排区间分为了 (l, j - 1) 和 (j, r)，且此时 i = j = 0，则会导致死循环，递归的层数无限增大。