AcWing 787. 归并排序
原题链接
简单
作者:
困了就睡
,
2023-05-08 20:14:18
,
所有人可见
,
阅读 87
//归并排序模板
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
public class Main {
static StreamTokenizer st=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static int[] arr=new int[100005];
static int[] temp=new int[100005];
public static void main(String[] args) throws IOException{
int n=next();
for (int i = 0; i < n; i++) {
arr[i]=next();
}
sort(arr,0,n-1);
for (int i = 0; i <n; i++) {
System.out.print(arr[i]+" ");
}
}
static int next() throws IOException{
st.nextToken();
return (int)st.nval;
}
static void sort(int[] arr,int l,int r){
if(l>=r){
return;
}
int mid=(l+r)>>1;
sort(arr,l,mid);
sort(arr,mid+1,r);
int k=0;
int i=l;
int j=mid+1;
while(i<=mid&&j<=r) {
if (arr[i] <= arr[j]) temp[k++] = arr[i++];
else temp[k++] = arr[j++];
}
while (i <= mid) temp[k++] = arr[i++];
while (j <= r) temp[k++] = arr[j++];
for(int m=l,q=0;m<=r;m++,q++) arr[m]=temp[q];
}
}