1.什么是歸并排序？
歸并：將兩個(gè)有序數(shù)組合并成一個(gè)更大的有序數(shù)組。
歸并排序有兩個(gè)主要操作：遞歸和合并。
要將一個(gè)數(shù)組排序，可以先（遞歸的）將它分半分別排序，然后將結(jié)果歸并起來(lái)，這就是歸并排序。
我們知道遞歸的主要思想是分治思想，而這也是歸并排序的思想。
2.歸并的抽象方法
歸并方法主要講數(shù)組左側(cè)（a[lo..mid]）和數(shù)組右側(cè)(a[mid+1..hi])歸并成一個(gè)有序的數(shù)組并將結(jié)果防止到a[lo..hi]中。
在下面的實(shí)現(xiàn)中，我們將借助一個(gè)輔助數(shù)組aux：
public static void merge(int[] a, int lo, int mid,int hi){
// i代表mid左側(cè)的角標(biāo)，j代表mid右側(cè)的角標(biāo)，每次向數(shù)組a中放入左側(cè)的元素時(shí)i++，向數(shù)組a中放入右側(cè)的元素時(shí)j++
int i = lo, j= mid;
//將原數(shù)組復(fù)制到輔助數(shù)組中
for(int k = lo;k <= hi; k++){
aux[k] = a[k];
}
for(int k = lo; k <= hi; k++){
//1.左側(cè)用盡取右側(cè)
if(i > mid) a[k] = aux[j++];
//2.右側(cè)取盡取左側(cè)
else if(j>hi) a[k] = aux[i++];
//3.左側(cè)元素大于右側(cè)元素時(shí)取右側(cè)
else if(a[i] > a[j]) a[k] = aux[j++];
//4.左側(cè)元素小于右側(cè)元素時(shí)取左側(cè)
else a[k] = aux[i++];
}
}
歸并完成后，下面要實(shí)現(xiàn)遞歸，遞歸的順序有兩種方式：
1.自頂向下
2.自底向上
3.自頂向下的歸并排序
public class Merge{
private static int[] aux;
public static void sort(int[] a){
//一次性分配空間
aux = new int[a.length];
mergeSort(a,0,a.length - 1);
}
//遞歸方法
private static void mergeSort(int[] a; int lo; int hi){
//跳出遞歸的條件
if(lo >= hi) return;
int mid = lo + (hi - lo)/2;
mergeSort(a,lo,mid);//將左側(cè)排序
mergeSort(a,mid,hi);//將右側(cè)排序
merge(a,lo,mid,hi);//歸并結(jié)果
}
}
4.自底向上的歸并排序
這種實(shí)現(xiàn)方法比標(biāo)準(zhǔn)的遞歸代碼量更少。首先我們進(jìn)行的是兩兩歸并（把每個(gè)元素想象成一個(gè)大小為1的數(shù)組），然后是四四歸并（將兩個(gè)大小為2的數(shù)組歸并成一個(gè)大小為4的數(shù)組），然后是八八歸并...
public class MergeBU {
public static void sort(int[] a) {
int n = a.length;
int[] aux = new Comparable[n];
for (int len = 1; len < n; len *= 2) {
for (int lo = 0; lo < n-len; lo += len+len) {
int mid = lo+len-1;
int hi = Math.min(lo+len+len-1, n-1);
merge(a, aux, lo, mid, hi);
}
}
}
}
自底向上的歸并.png
自底向上的歸并排序比較適合采用鏈表的數(shù)據(jù)，這種方法只需要重新組織鏈表鏈接就能將鏈表原地排序（不需要?jiǎng)?chuàng)建新的鏈表結(jié)點(diǎn)）。
5.復(fù)雜度
對(duì)于長(zhǎng)度為N的數(shù)組，歸并排序所需的時(shí)間和NlogN成正比；它的主要缺點(diǎn)是：所需要的額外空間和N成正比。
