C語言歸並排序（合並排序）算法及代碼

歸並排序也稱合並排序，其算法思想是將待排序序列分為兩部分，依次對分得的兩個部分再次使用歸並排序，之後再對其進行合並。僅從算法思想上了解歸並排序會覺得很抽象，接下來就以對序列A[0], A[l]…, A[n-1]進行升序排列來進行講解，在此采用自頂向下的實現方法，操作步驟如下。

(1)將所要進行的排序序列分為左右兩個部分，如果要進行排序的序列的起始元素下標為first，最後一個元素的下標為last，那麼左右兩部分之間的臨界點下標mid=(first+last)/2，這兩部分分別是A[first … mid]和A[mid+1 … last]。

(2)將上面所分得的兩部分序列繼續按照步驟(1)繼續進行劃分，直到劃分的區間長度為1。

(3)將劃分結束後的序列進行歸並排序，排序方法為對所分的n個子序列進行兩兩合並，得到n/2或n/2+l個含有兩個元素的子序列，再對得到的子序列進行合並，直至得到一個長度為n的有序序列為止。下面通過一段代碼來看如何實現歸並排序。

#include <stdio.h>
#include <stdlib.h>
#define N 7

void merge(int arr[], int low, int mid, int high){
    int i, k;
    int *tmp = (int *)malloc((high-low+1)*sizeof(int));
    //申請空間，使其大小為兩個
    int left_low = low;
    int left_high = mid;
    int right_low = mid + 1;
    int right_high = high;

    for(k=0; left_low<=left_high && right_low<=right_high; k++){  // 比較兩個指針所指向的元素
        if(arr[left_low]<=arr[right_low]){
            tmp[k] = arr[left_low++];
        }else{
            tmp[k] = arr[right_low++];
        }
    }

    if(left_low <= left_high){  //若第一個序列有剩余，直接復制出來粘到合並序列尾
    //memcpy(tmp+k, arr+left_low, (left_high-left_low+l)*sizeof(int));
    for(i=left_low;i<=left_high;i++)
        tmp[k++] = arr[i];
    }

    if(right_low <= right_high){
    //若第二個序列有剩余，直接復制出來粘到合並序列尾
    //memcpy(tmp+k, arr+right_low, (right_high-right_low+1)*sizeof(int));
        for(i=right_low; i<=right_high; i++)
            tmp[k++] = arr[i];
    }

    for(i=0; i<high-low+1; i++)
        arr[low+i] = tmp[i];
    free(tmp);
    return;
}

void merge_sort(int arr[], unsigned int first, unsigned int last){
    int mid = 0;
    if(first<last){
        mid = (first+last)/2; /* 注意防止溢出 */
        /*mid = first/2 + last/2;*/
        //mid = (first & last) + ((first ^ last) >> 1);
        merge_sort(arr, first, mid);
        merge_sort(arr, mid+1,last);
        merge(arr,first,mid,last);
    }
    return;
}

int main(){
    int i;
    int a[N]={32,12,56,78,76,45,36};

    printf ("排序前 \n");
    for(i=0;i<N;i++)
        printf("%d\t",a[i]);

    merge_sort(a,0,N-1);  // 排序

    printf ("\n 排序後 \n");
    for(i=0;i<N;i++)
        printf("%d\t",a[i]); printf("\n");

    system("pause");
    return 0;
}

運行結果：

排序前
32    12    56    78    76    45    36
排序後
12    32    36    45    56    76    78

分析上面的運行結果，通過歸並排序成功地實現了對給定序列的排序操作。接下來通過圖11-9來了解歸並排序的具體操作流程。

在圖11-9中，先對所要進行排序的序列進行分解，直到分為單個元素為止，然後將其進行兩兩合並。由於最終分解成單個元素，因此在合並的時候.將小數放在前面，大數放在後面，得到一個有序序列。接下來對兩個相連的有序序列進行排序，先比較有序序列中的第一個元素，將較小的元素放入臨時數組中，接著將較小元素所在數組的下一個元素與另一個數組中的較小元素比較，同樣將較小元素放入臨時數組中，依次進行，直到兩個數組的所有元素都放入臨時數組中，最後再將臨時數組的元素放入原始數組中的對應位置。


圖11-9歸並排序的操作流程