模板中每次归并需要建立一个临时数组,将数组两部分归并到临时数组再将临时数组拷贝回原数组。我对此将算法的时间复杂度进行稍稍的改进。新建一个辅助数组 aux[]
,并初始化将原数组元素拷贝到 aux
数组中。然后每次排序递归中交换原数组和辅助数组的角色,这样就省去了从临时数组拷贝回原数组的操作了。代码实现如下:
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) q[k] = aux[j++];
else if (j > r) q[k] = aux[i++];
else if (aux[i] <= aux[j]) q[k] = aux[i++];
else q[k] = aux[j++];
}
}
public static void sort(int[] q, int[] aux, int l, int r) {
if (l >= r) return;
int mid = (l + r) / 2;
sort(aux, q, l, mid);
sort(aux, q, mid + 1, r);
merge(q, aux, l, mid, r);
}
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n = input.nextInt();
int[] q = new int[n];
int[] aux = new int[n];
for (int i = 0; i < n; i++) aux[i] = q[i] = input.nextInt();
sort(q, aux, 0, n - 1);
for (int i = 0; i < n; i++) System.out.printf("%d ", q[i]);
}
}