資料結構與算法系列 -- 歸并排序

       歸并排序的核心思想還是蠻簡單的。如果要排序一個數組，我們先把數組從中間分成前後兩 部分，然後對前後兩部分分别排序，再将排好序的兩部分合并在一起，這樣整個數組就都有 序了。  如下圖，針對數組：11、   8、   3、  9、7、1、2、5，歸并排序的過程如下                                                                

僞代碼如下：  

void test(){

 merge_sort(data,0,data.length-1)

}



//對  數組data 下标為 r 到 q 進行排序
void  merge_sort(data,r,q){
   if(r>=q)
        return;

  int mid = (r + q)/2
  merge_sort(data,r,mid)
  merge_sort(data,mid+1,q)
  merge(data,r,mid,mid+1,q)



}

//将已經有序的 data[r1] ... data[q1] ,  data[r2] ... data[q2] ,合并排序為有序數組
void  merge(data,r1,q1,r2,q2){


}
           

  Java代碼如下：

public class SortTest {

    private void swap(int[] data,int i,int j){
           int tmp = data[i];
           data[i] = data[j];
           data[j] = tmp;
    }

    public void printArray(int[] data){
        for(int d:data){
            System.out.print(d+" ");
        }
        System.out.println();
    }

  
    /**
     * 歸并排序
     */
    public void mergeSort(int[] data,int r1,int q1,int r2,int q2){
        int start1 = r1;
        int start2 = r2;
        int start  = 0;
        int[] tmp = new int[q2-r1+1];
        while (start1<=q1 && start2 <=q2){
            if(data[start1] <= data[start2]){
                tmp[start++] = data[start1++];
            }else {
                tmp[start++] = data[start2++];
            }
        }

        while (start1<=q1){
             tmp[start++] = data[start1++];
        }

        while (start2<=q2){
            tmp[start++] = data[start2++];
        }

        for(int i=r1;i<=q2;i++){
            data[i] = tmp[i-r1];
        }

    }

    public void merge(int[] data,int r,int q){
        if(r>=q)
            return;

        int middle = (r+q)/2;
        merge(data,r,middle);
        merge(data,middle+1,q);
        mergeSort(data,r,middle,middle+1,q);

    }
    /**
     * 歸并排序
     */
    @Test
    public void test4(){
        int[]  data = {55,76,34,66,22,31,13,25,90,87,56,65,66};
        //int[]  data = {6,7,8,9,1,2,30,40,50};
        //mergeSort(data,0,3,4,8);
        merge(data,0,data.length-1);
        printArray(data);

    }
}
           

結果：

13 22 25 31 34 55 56 65 66 66 76 87 90 
           

分析：

第一，歸并排序是穩定的排序算法嗎？ 歸并排序穩不穩定關鍵要看 merge() 函數，也就是兩個有序子數組合并成一個有序數組的那部分代碼。 我們可以控制該函數在合并時，保證相同值元素 的先後順序不變。是以，歸并排序是一個穩定的排序算法。   第二，歸并排序的時間複雜度是多少？ 從我們的原理分析和僞代碼可以看出，歸并排序的執行效率與要排序的原始數組的有序程度 無關，是以其時間複雜度是非常穩定的，不管是最好情況、最壞情況，還是平均情況，時間 複雜度都是 O(nlogn)。   第三，歸并排序的空間複雜度是多少？ 歸并排序的時間複雜度任何情況下都是 O(nlogn)，看起來非常優秀。（待會兒你會發現， 即便是快速排序，最壞情況下，時間複雜度也是 O(n 2 )。）但是，歸并排序并沒有像快排那 樣，應用廣泛，這是為什麼呢？因為它有一個緻命的“弱點”，那就是歸并排序不是原地排 序算法。