快速排序

快速排序的工作原理是通过分治的方式来将一个数组排序。

步骤：

1. 找分界点x ，将数列划分为两部分 q[l] / q[l] / q[l + r >> 1]；
2. 使得分界点所有左边的数 <= x ，所以右边的数 >= x ；
3. 递归排序left，递归排序right

为什么用do ...; while () ，先移动一次？

怎么划分呢？常用[l, j] [j + 1, r]

[l, j] [j + 1, r]要注意的点

x不能取r索引的值，为什么？

划分二【不常用】

[l, i-1] [i , r]要注意的点

x不能取l索引的值，为什么？

同上

板子

void quick_sort(int q[], int l, int r){
    if (l >= r) return ;
    int i = l - 1,j = r + 1;
    int x = q[l + r >> 1];
    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);
}

另一种以i划分区间的因为不常用就不给出了