AcWing 787. 归并排序(JAva)
原题链接
简单
作者:
hxzz
,
2021-01-11 13:37:12
,
所有人可见
,
阅读 297
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int n = cin.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; ++ i) {
a[i] = cin.nextInt();
}
mergeSort(a, 0, n - 1, new int[n]);
for (int x : a) {
System.out.print(x + " ");
}
}
public static void mergeSort(int[] a, int l, int r, int[] c) {
if (l >= r) return;
int m = (l + r) >> 1;
mergeSort(a, l, m, c);
mergeSort(a, m + 1, r, c);
int i = l, j = m + 1;
for (int k = l; k <= r; ++ k) {
if (j > r || (i <= m && a[i] < a[j])) c[k] = a[i ++];
else c[k] = a[j ++];
}
for (int k = l; k <= r; ++ k) {
a[k] = c[k];
}
}
}