自頂向下歸并排序和自底向上的歸并排序

1. 歸并排序算法的使用情景

歸并排序算法和快速排序算法是java.util.Arrays中使用的排序算。對于一般的基本數據類型，Arrays.sort函數使用雙軸快速排序算法，而對于對象類型使用歸并排序（準確的說使用的是TimSort排序算法，它是歸并排序的優化版本）。這樣做的原因有兩點，第一個原因，歸并排序是穩定的，而快速排序不是穩定的。第二個原因，對于基本數據類型，排序的穩定性意義不大，但對于復合數據類型（比如對象）排序的穩定性就能幫助我們保持排序結果的某些性質。

2. 自頂向下的歸并排序

自頂向下的排序算法就是把數組元素不斷的二分，直到子數組的元素個數為一個，因為這個時候子數組必定是已有序的，然后將兩個有序的序列合并成一個新的有序的序列，兩個新的有序序列又可以合并成另一個新的有序序列，以此類推，直到合并成一個有序的數組。

為了體現歸并的排序的穩定性，我們的代碼使用java的泛型來實現對任意對象的排序。

public static <T extends Comparable<? super T>> 
    void MergeSortUpToDown(T[] A){
        @SuppressWarnings("unchecked")
        //創建合并兩個有序序列的輔助數組
        T[] aux = (T[])Array.newInstance(A.getClass().getComponentType(), A.length);
        mergeSortUpToDown0(A, aux, 0, A.length-1);
    }


public static <T extends Comparable<? super T>> 
void mergeSortUpToDown0(T[] A, T[] aux, int start, int end){
    if(start == end)
        return;
    int mid = (start+end)/2;
    mergeSortUpToDown0(A, aux, start, mid);
    mergeSortUpToDown0(A, aux, mid+1, end);
    //復制到輔助數組中,此時[start,mid] [mid+1, end]兩個子數組已經有序
    System.arraycopy(A, start, aux, start, end - start + 1);
    //然后歸并回來
    int i = start, j = mid+1, k;
    for(k = start; k <= end; k++){
        if(i > mid){
            A[k] = aux[j++];
        }else
        if(j > end){
            A[k] = aux[i++];
        }else
        if(aux[i].compareTo(aux[j]) <= 0){
            A[k] = aux[i++];
        }else{
            A[k] = aux[j++];
        }
    }
}</code></pre> 

3. 自底向上的歸并排序
 
  
自底向上的歸并排序算法的思想就是數組中先一個一個歸并成兩兩有序的序列，兩兩有序的序列歸并成四個四個有序的序列，然后四個四個有序的序列歸并八個八個有序的序列，以此類推，直到，歸并的長度大于整個數組的長度，此時整個數組有序。需要注意的是數組按照歸并長度劃分，最后一個子數組可能不滿足長度要求，這個情況需要特殊處理。自頂下下的歸并排序算法一般用遞歸來實現，而自底向上可以用循環來實現。
 
  
 
  
//自底向上歸并排序
    public static <T extends Comparable<? super T>> void MergeSortDownToUp(T[] A){
        @SuppressWarnings("unchecked")
        T[] aux = (T[])Array.newInstance(A.getClass().getComponentType(), A.length);
        int len,i,j,k,start,mid,end;
        //len表示歸并子數組的長度，1表示，一個一個的歸并，歸并后的長度為2,2表示兩個兩個的歸并，歸并后的長度為4,以此類推
        for(len = 1; len < A.length; len = 2*len){
            //復制到輔助數組中
            System.arraycopy(A, 0, aux, 0, A.length);
            //按照len的長度歸并回A數組，歸并后長度翻倍
            for(start = 0; start < A.length; start = start+2*len){
                mid = start + len - 1;
                //對于數組長度不滿足2的x次冪的數組，mid可能會大于end
                end = Math.min(start + 2*len - 1, A.length-1);
                i = start; 
                //mid大于end時,j必然大于end,所以不會引起越界訪問
                j = mid+1;
                //[start,mid] [mid+1, end]
                for(k = start; k <= end; k++){
                    if(i > mid){
                        A[k] = aux[j++];
                    }else
                    if(j > end){
                        A[k] = aux[i++];
                    }else
                    if(aux[i].compareTo(aux[j]) < 0){
                        A[k] = aux[i++];
                    }else{
                        A[k] = aux[j++];
                    }
                }
            }
        }
    }
 
  
4. 參考文章
 
  
[1] 算法（第四版）RobertSedgewick
 
  
 
 
  
來自：http://www.cnblogs.com/nullzx/p/5968170.html