AcWing 787. 归并排序(非递归写法Java)
原题链接
简单
作者:
acwing_542
,
2021-02-10 00:46:23
,
所有人可见
,
阅读 398
非递归写法
算法描述
共两层循环,外层循环是将 size 乘 2 , 其中 size 是归并的两个数组分别的大小。内层循环是 size 已经确定了,将数组以 size 大小为单位进行两两配对归并。
时间复杂度 $O(n\log (n))$
Java 代码
import java.util.Scanner;
public class Main {
public static void merge(int[] q, int[] aux, int l, int mid, int r) {
int i = l, j = mid + 1;
for (int k = l; k <= r; k++) {
if (i > mid) aux[k] = q[j++];
else if (j > r) aux[k] = q[i++];
else if (q[i] <= q[j]) aux[k] = q[i++];
else aux[k] = q[j++];
}
for (int k = l; k <= r; k++) q[k] = aux[k];
}
public static void sort(int[] q, int n) {
int[] aux = new int[n];
for (int size = 1; size < n; size *= 2)
for (int l = 0; l < n - size; l += size * 2)
merge(q, aux, l, l + size - 1, Math.min(l + 2 * size - 1, n - 1));
}
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n = input.nextInt();
int[] q = new int[n];
for (int i = 0; i < n; i++) q[i] = input.nextInt();
sort(q, n);
for (int i = 0; i < n; i++) System.out.printf("%d ", q[i]);
}
}