快排思路整理

quick_sort思路

1. 选取pivot
选择q[l+r>>1]作为pivot。
原因：若数组为有序且选取q[l]，则会进行每次左边界向右移动一位的递归。（取左边界的话，如果左区域只剩下一个数，则会死循环）

2. 进行排序
原则：先移动，再判断（所以初始化 i,j 应让其指向 l~r 外界一格）

3. 递归
递归处理左右两边。
取quick_sort(q,l,j) and quick_sort(q,j+1,r)
原因：pivot取下界值，进行排序后 i==j or i==j+1 ，即以j为界限。

核心代码

void quick_sort(int q[],int l,int r)
{
    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]);
    }

    quick_sort(q,l,j);//!!!
    quick_sort(q,j+1,r);
}