概要
歸并排序就是將一個數(shù)組分成前后兩部分征唬，分別排序礁扮，最后將結(jié)果歸并起來忿偷，形成一個有序的新數(shù)組蛉威。
- 優(yōu)點：數(shù)組排序所需時間與數(shù)組長度關(guān)系：NlogN
- 缺點：需要的額外空間與N成正比材蛛。原因：排好序的元素放到了新數(shù)組圆到，就占用了額外的空間。
因此卑吭，如果歸并一個很大的數(shù)組芽淡，進行多次歸并時，由于每次歸并都會創(chuàng)建一個新數(shù)組豆赏，那所占用的空間會很大挣菲，也會有好多麻煩。
原地歸并
如果能在原地歸并掷邦，不需要額外的空間的話白胀，那就能解決上述問題。
- java代碼：(將一個前后兩部分分別有序的數(shù)組原地歸并)
public static void merge(Comparable[] a, int lo, int mid, int hi)
{//將a[lo, mid]和a[mid + 1, hi]歸并
int i = lo, j = mid+1;
for (int k = lo; k <= hi; k++)//首先將a[lo...hi]復制到aux[lo...hi]
aux[k] = a[k];
for (int k = lo; k <=hi; k++)//歸并回到a[lo...hi]
if (i > mid) a[k] = aux[j++]; //左半邊取盡就取右半邊的元素
else if (i > mid) a[k] = aux[j++]; //右半邊取盡就取左半邊的元素
else if less(aux[j], aux[i])) a[k] = aux[j++];//兩邊都沒有取盡就比較儡率，把較小的取出來
else a[k] = aux[i++];
}
自頂向下的歸并排序
對子數(shù)組a[l0...hi]排序良蛮，將它分為a[l0...mid]和a[mid+1...hi]兩部分钉跷，分別地鬼調(diào)用他們單獨排序，最后將有序的兩個子數(shù)組歸并為最終的排序結(jié)果向抢。
- java代碼
public class Merge
{
private static Comparable[] aux; //歸并所需的輔助數(shù)組
public static void sort(Comparable[] a)
{
aux = new Comaparable[a.length];//一次性分配空間
sort(a, 0, a.length - 1);
}
private static void sort(Comparable[] a, int lo, int hi)
{
if (hi <= lo) return;
int mid = lo + (hi - lo)/2;
sort(a, lo, mid); //將左邊排序
sort(a, mid+1, hi);//將右邊排序
merge(a, lo, mid, hi);//歸并結(jié)果
}
}
- 代碼研究
歸并排序的代碼核心其實就是sort(Comparable[] a, int lo, int hi)函數(shù)不斷的自我調(diào)用。 -
以a[0...15]為例
sort()方法調(diào)用自己將左半部分a[0...7]排序胚委，再在其中調(diào)用自己將左半部分a[0...3]排序挟鸠，再調(diào)用自己將a[0...3]左半部分a[0...1]排序。然后將a[0...3]右半部分a[2...3]排序亩冬，最后a[0...3]左右部分合并兄猩。。。枢冤。軌跡圖如圖一所示：
圖一：自頂向下的歸并排序的調(diào)用軌跡
