排序算法之歸并排序   

羅朝輝（http://www.shnenglu.com/kesalin）

轉載請注明出處

排序是數據處理中經常使用的一種重要運算，在計算機及其應用系統中，花費在排序上的時間在系統運行時間中占有很大比重，其重要性勿需多言。下文將介紹常用的如下排序方法，對它們進行簡單的分析和比較，并提供 C 語言實現。

所謂排序，就是要將一堆記錄，使之按關鍵字遞增(或遞減)次序排列起來。根據排序所采用的策略，可以分為如下五種：

1、插入排序（直接插入排序、希爾排序）

2、交換排序（冒泡排序、快速排序）

3、選擇排序（直接選擇排序、堆排序）
    4、歸并排序；

5、桶排序（桶排序，基數排序）；

---------------------------------------------------------------------------------

前面講了插入排序，交換排序，選擇排序，下面接著來講歸并排序。

歸并排序(Merge Sort)是利用"歸并"技術來進行排序。歸并是指將若干個已排序的子文件合并成一個有序的文件。

歸并排序

基本思想：設兩個有序的子序列(相當于輸入序列)放在同一序列中相鄰的位置上：array[low..m]，array[m + 1..high]，先將它們合并到一個局部的暫存序列 temp (相當于輸出序列)中，待合并完成后將 temp 復制回 array[low..high]中，從而完成排序。

在具體的合并過程中，設置 i，j 和 p 三個指針，其初值分別指向這三個記錄區的起始位置。合并時依次比較 array[i] 和 array[j] 的關鍵字，取關鍵字較小（或較大）的記錄復制到 temp[p] 中，然后將被復制記錄的指針 i 或 j 加 1，以及指向復制位置的指針 p 加 1。重復這一過程直至兩個輸入的子序列有一個已全部復制完畢(不妨稱其為空)，此時將另一非空的子序列中剩余記錄依次復制到 array 中即可。

下面是合并過程的 C 代碼實現:
   

void merge(int* array, int low, int mid, int high)
{
    assert(array && low >= 0 && low <= mid && mid <= high);

    int* temp = (int*)malloc((high - low + 1) * sizeof(int));
    if (!temp) {
        printf("Error:out of memory!");
        return;
    }

    int i = low;
    int j = mid + 1;
    int index = 0;

    while (i <= mid && j <= high) {
        if (array[i] <= array[j]) {
            temp[index++] = array[i++];
        }
        else {
            temp[index++] = array[j++];
        }
    }

    while (i <= mid) {
        temp[index++] = array[i++];
    }

    while (j <= high) {
        temp[index++] = array[j++];
    }

    memcpy((void*)(array + low), (void*)temp, (high - low + 1) * sizeof(int)) ;

    free(temp);
}

   歸并排序有兩種實現方法：自底向上和自頂向下。

自底向上方法，也就是常說的二路歸并排序，其基本思想是：第 1 趟排序將長度為 n 的待排序記錄看作 n 個長度為 1 的有序子序列，然后將這些子序列兩兩合并。完成第 1 趟排序之后，將得到 lgn 個長度為 2 的有序子序列（如果 n 為奇數，則最后還有一個長度為 1 的子序列）。第 2 趟排序是在第 1 趟的排序的基礎上，將這 lgn 個長度為 2 的子序列兩兩合并。如此反復，直到最后得到一個長度為n的有序文件為止。從這個排序過程來看，二路歸并排序是從將長度為 1 的子序列排序變化到長度為 n 的有序序列，因而是自底向上的。

下面是二路歸并排序的 C 代碼實現：
   

// 對 [0, length - 1] 做一趟歸并長度為 n  的歸并排序
void merge_pass(int* array, int length, int n)
{
    assert(array && length >= 1 && n >= 1);

    int i;
    int sortLength = 2 * n;

    // 歸并長度為 n 的兩個相鄰子序列
    for(i = 0; i + sortLength - 1 < length; i = i + sortLength) {
        merge(array, i, i + n - 1, i + sortLength - 1);
    }

    // 若 i + n - 1 < length - 1，則剩余一個子文件輪空，無須歸并。
    // 尚有兩個子序列，其中后一個長度小于 n, 歸并最后兩個子序列。
    if (length - 1 > i + n - 1) {
        merge(array, i, i + n - 1, length - 1);
    }
}

// 用分治法自下向上進行二路歸并排序
//
void merge_sort(int* array, int length)
{
    assert(array && length >= 0);

    int n;

    for(n = 1; n < length; n = (n << 1)) {
        merge_pass(array, length, n);
    }
}

   
   自底向上的二路歸并排序算法雖然效率較高，但可讀性較差（循環實現比遞歸實現一般效率都要高些）。下面來看看自上而下的遞歸實現，其可讀性要好得多。自上而下的方法是采用分治法思想，具體排序過程分成三個過程：

（1）分解：將當前區間一分為二，即求分裂點 mid = (low + high)/2; 

（2）求解：遞歸地對兩個子區間 array[low..mid] 和 array[mid + 1..high] 進行歸并排序；遞歸的終結條件：子區間長度為 1（一個記錄自然有序）。

（3）合并：將已排序的兩個子區間R[low..mid]和R[mid + 1..high]歸并為一個有序的區間 array[low..high]。

下面即是自上而下方法的 C 代碼實現：
   

void merge_sort_dc_impl(int* array, int low, int high)
{
    assert(array && low >= 0);

    int mid;
    if (low < high) {
        mid = (low + high) >> 1;

        merge_sort_dc_impl(array, low, mid);
        merge_sort_dc_impl(array, mid + 1, high);

        merge(array, low, mid, high);
    }
}

// 用分治法自上向下進行排序
void merge_sort_dc(int* array, int length)
{
    assert(array && length >= 0);

    merge_sort_dc_impl(array, 0, length - 1);
}