归并排序
-自然语言描述：
指的是将两个已经排序的序列合并成一个序列的操作。
归并过程为：比较a[i]和a[j]的大小，若a[i]≤a[j]，则将第一个有序表中的元素a[i]复制到r[k]中，并令i和k分别加上1；否则将第二个有序表中的元素a[j]复制到r[k]中，并令j和k分别加上1，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。
-原地归并的抽象方法：
public static void merge(Comparable[] a, int start, int mid, int end){
//将a[start..mid]和a[mid +1...end]归并
int i = star, j= mid + 1;
for(int k = start; k<=end; k++) //将a[start...end]复制到aux[start...end]
aux[k] = a[k];
for (int k = start; k<=end; k++)
if (i > mid) a[k] = aux[j++];
else if (j > end) a[k] = aux[i++];
else if (less(aux[j], aux[i])) a[k] = aux[j++];
else a[k] = aux[i++];
}
轨迹图
-自顶向下的归并排序：
public class Merge {
private static Comparable[] aux; // 归并所需的辅助数组
public static void sort(Comparable[] a){ // 一次性分配空间
aux = new Comparable[a.length];
sort(a, 0, a.length - 1);
}
private static void sort(Comparable[] a, int start, int end){
if (end <= start) return;
int mid = start + (end - start)/2;
sort(a, start, mid); //将左半边排序
sort(a, mid+1, end); //将右半边排序
merge(a, start, mid, end); //原地归并的抽象方法
}
}
自顶向下的归并排序的轨迹
调用轨迹
这两张图我也是想了好久才看懂一些，建议可以在纸上用二叉树画出来，会清晰很多。
-自底向上的归并排序
public class MergeBU {
private static Comparable[] aux; //归并辅助函数
public static void sort(Comparable[] a){
int N = a.length;
aux = new Comparable[N];
for (int sz = 1; sz < N; sz = sz + sz)
for (int lo = 0; lo < N - sz; lo += sz + sz)
merge(a, lo, lo + sz - 1,Math.min(lo + sz + sz - 1,N - 1));
}
}
自底向上的归并排序
