优点:所需时间和NlogN成正比
缺点:需要额外的内存用来存储辅助数组
/**
* Created by Administrator on 2016/10/8.
*/
public class MergeSort {
private static int copy[];
/*
原地归并
*/
private static void merge(int[] a, int l, int m, int h) {
int i = l, j = m + 1;//i,j分别为左右数组的第一个
for (int k = l; k <= h; k++)
copy[k] = a[k];
for (int k = l; k <= h; k++) {
if (i > m) a[k] = copy[j++];//左边取完
else if (j > h) a[k] = copy[i++];//右边取完
else if (copy[i] > copy[j]) a[k] = copy[j++];//右边最小 小于 左边最小
else a[k] = copy[i++];//右边最小 大于 左边最小
}
}
private static void mergeSort(int[] a, int l, int h) {
int m = (l + h) / 2;
if (h <= l) return;
mergeSort(a, l, m);
mergeSort(a, m + 1, h);
merge(a, l, m, h);
}
private static void mergeSort(int[] a) {
copy = new int[a.length];
mergeSort(a,0,a.length-1);
}
public static void main(String[] args) {
int[] a = {12,30,59,74,39,85,681,234,9444,55,46,39,1,69,2346,4545,55,31};
mergeSort(a);
for (int i : a)
System.out.print(i + ", ");
}
}
