排序

void quicksort(int q[],int l,int r){
    
    //递归终止的情况
    if(l>=r)return;
    
    //子问题处理
    int mid=q[l+r>>1],i=l-1,j=r+1;   //quicksort中的mid为数而不是下标
     //>>1速度比/2更快			//取中值比取随机值更快，且能防止因为边界问题导致死循环
    
    while(i<j){         //不需要=，i==j便停止     
        do i++;while(q[i]<mid);   //=mid时也停止可以有效防止越界（需要理解这点）
        do j--;while(q[j]>mid); //该操作使i,j交点处左边的数均小于mid，右边的数均大于mid
        if(i<j)swap(a[i],a[j]);   //大于等于时不用交换
    }
    
    //递归处理子问题
    quicksort(q,l,j),quicksort(q,j+1,r);   //i不一定==j
}

//注l，r相邻时，意qsort(l,r)不能分治为qsort(l,r)否则会死循环
//(l+r)>>1 =l
//quicksort(q,l,l),quicksort(q,r,r);   //正确
//quicksort(q,l,i),quicksort(q,i+1,r);   -->  quicksort(q,l,r),quicksort(q,r+1,r);错误

void qsort1(int a[],int l,int r){
	if(l >= r)return ;
	int mid = a[l + r >> 1],i = l - 1, j = r + 1;  		//int mid = a[l + r + 1>> 1]
	while(i < j){
		do i ++;while(a[i] < mid);
		do j --;while(a[j] > mid);
		if(i < j)swap(a[i],a[j]);
	}
	qsort1(a,l,j),qsort1(a,j + 1,r);   		//qsort1(a,l,i),qsort1(a,i + 1,r);
}"排序后(从小到大)"
void qsort2(int a[],int l,int r){
	if(l >= r)return ;
	int mid = a[l + r >> 1],i = l - 1, j = r + 1;
	while(i < j){
		do i ++;while(a[i] > mid);   //符号相反 
		do j --;while(a[j] < mid);
		if(i < j)swap(a[i],a[j]);
	}
	qsort2(a,l,j),qsort2(a,j + 1,r);
}"排序后(从小到大)"

bool cmp(int a,int b){
	return a > b;
}

"排序后(从小到大):  "	sort(a,a+n);   //qsort1(a,a,n);   
"排序后(从小到大):  "	sort(a,a+n,cmp);   //qsort2(a,a,n);

void mergesort(int q[],int l,int r){
    //递归的终止情况
    if(l>=r)return;    //相等就不用再排序啦
    
    //第一步：分成子问题
    int mid=l+r>>1;
    
    //第二步：递归处理子问题
    mergesort(q,l,mid),mergesort(q,mid+1,r);  //分治
    
    //第三步：合并子问题
    int k=0,i=l,j=mid+1;
    while(i<=mid&&j<=r){    //=压入最后一个元素
        if(q[i]<=q[j])temp[k++]=q[i++];         //一般第一短优先，大于时从大到小排序，小于号时从小到大排序
        else temp[k++]=a[j++];
    }
    while(i<=mid)temp[k++]=q[i++];
    while(j<=r)temp[k++]=q[j++];     //另一端末端
    
    for(int i=l,k=0;i<=r;i++)q[i]=temp[k++];   //返回原数组
}

//注意temp如果在函数中定义的话不要t[N]