AcWing 787. 归并排序
原题链接
简单
作者:
Lumos_18
,
2024-03-05 18:10:05
,
所有人可见
,
阅读 26
递归排序-JAVA
//递归排序
//先确定分界点,两边递归,然后才是合并(与快排方法顺序不同,快排是先排再递归)
//java中要注意静态方法只能调用静态的(方法,常量)
import java.util.Scanner;
public class Main {
static int N = 100008;
static int[] tmp = new int[N];
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 i = l, j = mid + 1, k = 0;
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) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] q = new int[n];
for (int i = 0; i < n; i++) {
q[i] = scanner.nextInt();
}
merge_sort(q, 0, n - 1);
for (int i = 0; i < n; i++) {
System.out.print(q[i] + " ");
}
}
}