// 归并排序算法模板(选用)
public static 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[] res = new int[r-l+1];
//两个排好序的数组 合并起来到 临时结果数组
int i=l,j=mid+1,k=0;
while(i<=mid&&j<=r){
if(q[i]<q[j])res[k++]=q[i++];
else res[k++]=q[j++];
}
//剩下的直接拼在结果数组后面
while(i<=mid)res[k++]=q[i++];
while(j<=r)res[k++]=q[j++];
//将临时结果数组 重新赋值给 q
for(int m=l,n=0;m<=r;m++,n++ )q[m]=res[n];
}
其他模板(向上取整)
public static void mergeSort(int[] q,int l,int r){
if(l>=r)return;
int mid = l+r+1>>1; //取向上取整的中点
//递归处理子问题
mergeSort(q,l,mid-1);
mergeSort(q,mid,r);
//临时结果数组
int[] res = new int[r-l+1];
//两个排好序的数组 合并起来到 临时结果数组
int i=l,j=mid,k=0;
while(i<=mid-1&&j<=r){
if(q[i]<q[j])res[k++]=q[i++];
else res[k++]=q[j++];
}
//剩下的直接拼在结果数组后面
while(i<=mid-1)res[k++]=q[i++];
while(j<=r)res[k++]=q[j++];
//将临时结果数组 重新赋值给 q
for(int m=l,n=0;m<=r;m++,n++ )q[m]=res[n];
}
输入输出
public static void main(String[] args)throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
String[] strs = br.readLine().split(" ");
int[] q = new int[n];
for(int i=0;i<n;i++)q[i]=Integer.parseInt(strs[i]);
mergeSort(q,0,n-1);
for(int i=0;i<n;i++){
if(i==n-1) System.out.print(q[i]);
else System.out.print(q[i]+" ");
}
}
棒啊