快速排序:分治思想，递归

分治过程

1. 确定分界点x：取边界值q[l]，取中间值q[(l+r)/2]，取随机值q[(rand()%(r-l+1))+l]；
2. 调整区间：分界点x左边都 <= x ；分界点x右边都 >= x ；(重点)
3. 递归处理左右两段；

 #include <iostream>

using namespace std;

const int N=1e6+10;
int q[N];
int n;

void quick_sort(int q[],int l,int r){
    if(l>=r) return; //递归的出口
    int x = q[l+r>>1],i=l-1,j=r+1; //分界点x取中间值，+优先于>>，所以l+r>>1等价于(l+r)/2
    while(i<j){ //i=j时，本次区间调整完毕
        do i++; while(q[i]<x); //i从左往右扫描，直到q[i] >= 分界点x时退出循环
        do j--; while(q[j]>x); //j从右往左扫描，直到q[j] <= 分界点x时退出循环
        if(i<j) swap(q[i],q[j]);//两个指针没有相遇，则交换
    }
    quick_sort(q,l,j); //递归处理左端，取j时，x一定不能取到q[r]
    quick_sort(q,j+1,r); //递归处理右端
}

int main(){
    scanf("%d",&n);
    for(int i=0;i<n;++i)   scanf("%d",&q[i]);

    quick_sort(q,0,n-1);

    for(int i=0;i<n;++i)   printf("%d ",q[i]);
    return 0;
}