import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class 归并排序 {
public static int[] tmp = new int[Integer.MAX_VALUE];
public static void mergeSort(int[] arr, int l, int r){
if (l >= r){
return;
}
// 确定分界点
int mid = l + r >> 1;
int i = l, j = mid + 1;
// 递归分区间
mergeSort(arr,l,mid);
mergeSort(arr,mid+1,r);
//归并内容
int k = 0;
while (i <= mid && j <= r){
if (arr[i] < arr[j]){
tmp[k++] = arr[i++];
}else {
tmp[k++] = arr[j++];
}
}
while (i <= mid){
tmp[k++] = arr[i++];
}
while (j <= r){
tmp[k++] = arr[j++];
}
// 回归原本数组
for (int m = 0,n = l; n <= r; m++,n++) {
arr[n] = tmp[m];
}
}
public static void main(String[] args) throws IOException {
int n;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
int[] arr = new int[n];
String[] strings = br.readLine().split(" ");
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(strings[i]);
}
mergeSort(arr,0,n-1);
for (int i = 0; i < n; i++) {
System.out.print(arr[i]+" ");
}
}
}
标签:归并,arr,int,mid,io,import,排序
From: https://www.cnblogs.com/YaoMa/p/18007192