AcWing 787. 归并排序-java
原题链接
简单
作者:
单箭头
,
2019-06-10 13:47:50
,
所有人可见
,
阅读 1077
java 代码
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int[] arr=new int[n];
for(int i=0;i<n;i++)
arr[i]=sc.nextInt();
MergeSort(arr,0,n-1);
for(int i=0;i<n;i++)
System.out.print(arr[i]+" ");
}
private static void MergeSort(int[] arr,int l,int r){
if(l>=r) return;
int mid=(l+r)/2;
MergeSort(arr,l,mid);
MergeSort(arr,mid+1,r);
merge(arr,l,r);
}
private static void merge(int[] arr,int l,int r){
int mid=(l+r)/2;
int[] tmp=new int[r-l+1];
int i=l,j=mid+1,k=0;
while(i<=mid && j<=r){
tmp[k++]=arr[i]>=arr[j]?arr[j++]:arr[i++];
}
while(i<=mid) tmp[k++]=arr[i++];
while(j<=r) tmp[k++]=arr[j++];
i=0;
while(l<=r){
arr[l++]=tmp[i++];
}
}
}