快速排序

愿天下的每个OIer都被善待

不讲原理了，不证复杂度了，上代码：

#include<iostream>
#include<cstdlib>
using namespace std;
void qsort(int* begin,int* end){//区间左闭右开
    if(begin>=end)return;//没有元素还排个寄
    int mid=*(begin+rand()%(end-begin));//随机边界，大样本容量下容易选到靠中间的值作为分界
    int *l=begin,*r=end-1;//左右指针
    while(l<=r){
        while(*l<mid)//找到从左数一个大于等于mid的
            l++;
        while(*r>mid)//找到从右数一个小于等于mid的
            r--; 
        if(l<=r){//能换？
            swap(*l,*r);//就换
            l++;//下一个，否则
            r--;//就会死循环
        }
    }
    qsort(begin,r+1);//递归左区间
    qsort(l,end);//递归右区间
}
int a[100005];
int n;
int main(){
    srand(time(0));//随机种子
    cin>>n;
    for(int i=0;i<n;i++)cin>>a[i];
    qsort(a,a+n);
    for(int i=0;i<n;i++)cout<<a[i]<<' ';
    return 0;
}