歸并排序
-自然語言描述：
指的是將兩個已經(jīng)排序的序列合并成一個序列的操作泡孩。
歸并過程為：比較a[i]和a[j]的大小矾湃，若a[i]≤a[j]宗雇，則將第一個有序表中的元素a[i]復(fù)制到r[k]中，并令i和k分別加上1螺捐；否則將第二個有序表中的元素a[j]復(fù)制到r[k]中码秉，并令j和k分別加上1逮矛，如此循環(huán)下去，直到其中一個有序表取完转砖，然后再將另一個有序表中剩余的元素復(fù)制到r中從下標(biāo)k到下標(biāo)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]復(fù)制到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; // 歸并所需的輔助數(shù)組
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); //原地歸并的抽象方法
}
}
自頂向下的歸并排序的軌跡
調(diào)用軌跡
這兩張圖我也是想了好久才看懂一些鲸伴，建議可以在紙上用二叉樹畫出來，會清晰很多晋控。
-自底向上的歸并排序
public class MergeBU {
private static Comparable[] aux; //歸并輔助函數(shù)
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));
}
}
自底向上的歸并排序
