引言

快速排序是什么？快速的排序！🤣 平均时间复杂度O(nlogn)

快速排序跟二分和归并排序一样，也属于分治算法。

而分治算法可粗略分成三步。

（1）分解成可解的子问题
（2）求解子问题
（3）合并子问题的解并构成原问题的解。

快速排序的粗略概括

随机从一个待排序区间取一个数x，将区间分成两个区间，

第一区间所有数>= x ,第二区间所有数 <= x 。

然后两个区间各自再随机从自身区间取一个数x，将其自身再次分成两个区间，

同样的，其子第一区间所有数>= x ,子第二区间所有数 <= x 。

如此往复，最终直到区间为空或只有一个数。相当于排序好了。

聪明的小伙伴对加粗字体很敏感，啪的一下，反应很快啊~

随机？若取左右边界的值，当待排序列已经排好序，

那么划分的两个区间大小严重失衡！时间复杂度退化成O(n^2)。

当然取中点值也可以避免这种情况。

分成两个区间 ? 分治算法第一步，分解成可解的子问题

最终直到区间为空或只有一个数？这个是递归终止条件

快速排序双指针模板（从小到大）

void quick_sort(int q[], int l, int r)
{
    //递归的终止条件
    if(l >= r) return;
    //第一步：分成子问题
    int x = q[l + r >> 1];//取中间值作为 x 
    //int x = q[rand() % len];//取随机值作为 x
    int i = l - 1, j = r + 1;//下面有do, 为了处理边界值，要先把范围扩大。
    while(i < j)
    {
        do i++; while(q[i] < x);//从左到右，找不小于x的值q[i]
        do j--; while(q[j] > x);//从右到左，找不大于x的值q[j]
        if(i < j) swap(q[i], q[j]);//区间元素个数大于1时交换q[i]和q[j]
    }
    //循环结束时  j <= i , x <= q[i], q[j] <= x, q[l..i - 1] <= x, x <= q[j + 1..r] 
    //所以         q[l..j] <= x, x <= q[j + 1, r]
    //第二步：递归求解子问题
    quick_sort(q, l, j), quick_sort(q, j + 1, r);
    //第三步：快速排序的子问题合并说自动完成的。
}

至于快速排序双指针模板（从大到小）.

只需要把上面两个do..while()里的<>互换就可以了

总结

1.找到x = q[l] 或 q[l + r >> 1] 或 q[l] 或 q[区间随机数]。
2.另左边所有数[l..j] <= x ， 右边所有数[j + 1, r] >= x。
3.递归排序[l..j] 和 [j + 1, r]。