AcWing 787. 归并排序
原题链接
简单
作者:
一天一杯AD钙奶
,
2024-01-13 19:42:48
,
所有人可见
,
阅读 40
Java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static final int N = (int)1e6 + 10;
static int[] q = new int[N];
static int[] tmp = new int[N];
public static void merge_sort(int[] q, int l, int r){
if(l >= r) return;
int mid = (l + r) >>> 1;
merge_sort(q, l ,mid);
merge_sort(q, mid + 1, r);
int k = 0, i = l, j = mid + 1;
while(i <= mid && j <= r){
if(q[i] <= q[j]) tmp[k ++] = q[i ++];
else tmp[k ++] = q[j ++];
}
while(i <= mid) tmp[k ++] = q[i ++];
while(j <= r) tmp[k ++] = q[j ++];
for(i = l, j = 0; i <= r; i ++, j++) q[i] = tmp[j];
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
String[] elements = br.readLine().split(" ");
for(int i = 0; i < n; i ++) q[i] = Integer.parseInt(elements[i]);
merge_sort(q, 0 , n - 1);
for (int i = 0; i < n - 1; i++) System.out.print(q[i] + " ");
System.out.println(q[n - 1]);
}
}