排序算法之Merge Sort

Merge Sort 根本思路（設計算複雜度為 T(n)）：

1) 序列一分為二 //計算複雜度為O(1);

2) 子序列遞歸排序 //計算複雜度為 2*T(n/2);

3) 合并有序子序列 // 計算複雜度為 O(n);

是以可以得出 T(n) = 2*T(n/2) + O(n);

則可得 T(n) = O(n*log(n))

在歸并排序中最核心的問題就是如何合并兩個有序的序列，我們利用的方法是二路歸并算法。

簡單來說就是：隻比較兩個序列的開頭位置，取出其中小的那一個，然後循環運作，知道兩個序列歸并到一起。

一下是C語言的代碼：

//
//  main.c
//  mergeSortV2
//
//  Created by HanXia on 18/3/14.
//  Copyright © 2018年 HanXia. All rights reserved.
//

#include <stdio.h>
void merge(int *a, int lo, int mid, int hi);
void mergeSort(int *a, int lo, int hi){
    if (hi - lo <= 1){
        return;
    }
    else {
        int mid = (hi + lo) >> 1;
        //将問題一分為二
        mergeSort(a, lo, mid); //遞歸調用mergeSort函數
        mergeSort(a, mid,hi);  //遞歸調用mergeSort函數
        merge(a, lo, mid, hi); //歸并兩個序列
    }
}
//二路歸并算法
void merge(int *a, int lo, int mid, int hi){
    int lb = mid - lo;
    //定義B數組将一部分資料copy出來 以下C數組為a[mid,hi] A[lo, hi]
    int B[lb];
    for(int i = 0; i < lb; i++){
        B[i] = a[lo + i];
    }
    //因為我們并沒有開辟新的C數組，是以當B 插入完畢後算法結束
    //同時一下判斷 hi <= k 與 k < hi 相當于在 a[hi] 設定為一個無窮大的數
    //以便于在C歸并完後可以順利歸并B數組在正确的位置
    for(int i = lo, j = 0, k = mid; j < lb;){
        if (hi <= k || B[j] <= a[k]){ //這裡的a[k]為C數組部分
            //B 數組中的首相小于等于C數組中首相（注如果此時數組C以及插入完畢，則總是成立）
            a[i] = B[j];  //取出B數組中的首相
            j++;
            i++;
        }
        if (k < hi && a[k] < B[j]){ //
            a[i] = a[k];
            i++;
            k++;
        }
    }
}

int main(int argc, const char * argv[]) {
    int a [10] = {1, 2, 4, 5, 3, 2, 5, 8, 10, 1};
    int lo = 2;
    int hi = 8;
    mergeSort(a, lo, hi);
    for(int i = lo ; i < hi; i++){
        printf("a[%d] = %d\n",i,a[i]);
    }
    return 0;
}
           

輸出為：

a[2] = 2
a[3] = 3
a[4] = 4
a[5] = 5
a[6] = 5
a[7] = 8