快速排序

代码模板

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

代码原理

扫描

​ 函数需要读入三个数值，一个是通过指针引入数组q[]，另外两个分别是数组的左端点和右端点，在这里设置为l和r在代码中随机取一个位置e.g. x= q[l+r>>1]，作为分界点x=q[]，然后使用两个指针，一个从前向后扫描数组，一个从后向前扫描数组。其中命名从前向后扫描数组的指针为i，而从后向前扫描数组的指针叫为j，然后开始扫描。

​ 在扫描过程中，在这里以从小到大排序为例，因为小的数字需要排列在前面，所以在i从前向后扫描的时候，如果遇到了比q[x]更大的数字则停止继续扫描，这个时候让j从后向前开始扫描，如果遇到了比q[x]更小的数字则停止扫描。

​ Tips:由于--j比++i要后运行，实际情况下常常为j穿过i，而i的位置往往不一定是分界位置，所以尽量取j作为分界位置

交换

​ 由于最后输出的需要是小的数字在前面，而大的数字在后面，所以在扫描都停止以后，将j指向的小数字和i指向的大数字相互交换位置，就可以把他们正确的放于左边小于q[i]，右边大于q[i]，然后再一直进行扫描，直到i和j重合或者穿过的时候停止扫描，然后再通过递归的方式进行多次分段扫描，直到所有的函数都不能再进行交换(if(l>=r) return;)就返回最后的数值。

​ Ps：在一次扫描+交换结束以后，i左边的所有数字一定小于x，而j右边的数字一定大于x

时间复杂度

O(n*logn)

注意

1. 取x的时候如果用位运算，只需要>>1即可，不要移动多了，不然会出现越界或者其他特殊情况（记住模板就好）
2. 在分治的qsort中（e.g. qosrt(l,j,q)）如果取j则在上方取x=q[？]中绝对不能取x=q[r]的情况，不然会出现由于边界问题导致的死循环。快捷记忆的方法为：如果x取了右端点，则分治不为右。如果x取了左端点，则分治不为左