前提:不能有重复
快速排序代码
void quick_sort(int a[],int l,int r){
if(l>=r) return;
int x=a[l];int i=l;int j=r;
while(i<j){
while(a[i]<x) i++;//x左边找到第一个大于等于x的
while(a[j]>x) j--;//x右边找到第一个小于等于x的
//交换,最后i=j时会出现自己和自己交换的情况,可以加上if(i<j)语句
int t=a[i];a[i]=a[j];a[j]=t;
}
//第一遍排完之后应该是i=j=index_x
//递归
quick_sort(a,l,i-1);
quick_sort(a,j+1,r);
}
归并排序代码
int temp[N];
void merge_sort(int a[],int l,int r){
if(l>=r) return;
int mid=l+(r-l)/2;//注意+-优先级比>>高,如果用>>要写成mid=l+((r-l)>>1);
merge_sort(a,l,mid);merge_sort(a,mid+1,r);//不断二分,直到最小r-l=1
//l到mid是排好序的,mid+1到r是排好序的,所以从l和mid+1开始,将l到r之间排好序
int k=0,i=l,j=mid+1;
while(i<=mid && j<=r){
if(a[i]<a[j])temp[k++]=a[i++];
else temp[k++]=a[j++];
}
//如果一边已经排完了,另一边还有没排完的,直接按序接在后面即可
while(i<=mid)temp[k++]=a[i++];
while(j<=r)temp[k++]=a[j++];
//将temp中0到k-1个数写到a中l到r的位置
for(i=l,j=0;i<=r;i++,j++)a[i]=temp[j];
}