C語言歸併排序演算法

用歸併排序法對一組資料由小到大進行排序，資料分別為 695、458、362、789、12、 15、163、23、2、986。

實現過程：

(1) 自定義函數 merge()，實現一次歸併排序。

(2) 自定義函數 merge_sort()，實現歸併排序。

(3) 程式程式碼如下：

#include <stdio.h>
int merge(int r[],int s[],int x1,int x2,int x3)    //自定義實現一次歸併樣序的函數
{
    int i,j,k;
    i=x1;    //第一部分的開始位置
    j=x2+1;  //第二部分的開始位置
    k=x1;
    while((i<=x2)&&(j<=x3))    //當i和j都在兩個要合併的部分中時
        if(r[i]<=r[j])    //篩選兩部分中較小的元素放到陣列s中
        {
            s[k] = r[i];
            i++;
            k++;
        }
        else
        {
            s[k]=r[j];
            j++;
            k++;
        }
        while(i<=x2)    //將x1?x2範圍內未比較的數順次加到陣列r中
            s[k++]=r[i++];
        while(j<=x3) //將x2+l?x3範圍內未比較的數順次加到陣列r中
            s[k++]=r[j++];
    return 0;
}

int merge_sort(int r[],int s[],int m,int n)
{
    int p;
    int t[20];
    if(m==n)
        s[m]=r[m];
    else
    {
        p=(m+n)/2;
        merge_sort(r,t,m,p);    //遞回呼叫merge_soit()函數將r[m]?r[p]歸併成有序的t[m]?t[p]
        merge_sort(r,t,p+1,n);    //遞回一呼叫merge_sort()函數將r[p+l]?r[n]歸併成有序的t[p+l]?t[n]
        merge(t,s,m,p,n);    //呼叫函數將前兩部分歸併到s[m]?s[n】*/
    }
    return 0;
}

int main()
{
    int a[11];
    int i;
    printf("請輸入10個數：n");
    for(i=1;i<=10;i++)
        scanf("%d",&a[i]);    //從鍵盤中輸入10個數
    merge_sort(a,a,1,10);    //呼叫merge_sort()函數進行歸併排序
    printf("排序後的順序是：n");
    for(i=1;i<=10;i++)
        printf("%5d",a[i]);    //輸出排序後的資料
    printf("n");
    return 0;
}

執行結果：

請輸入10個數：
695 458 362 789 12 15 163 23 2 986
排序後的順序是：
    2   12   15   23  163  362  458  695  789  986

技術要點：

歸併是將兩個或多個存序記錄序列合併成一個有序序列。歸併方法有多種，一次對兩個有序記錄序列進行歸併，稱為路歸併排序，也有三路歸併排序及多路歸併排序。本範例是二路歸併排序，基本方法如下：

(1) 將 n 個記錄看成是 n 個長度為 1 的有序子表。

(2) 將兩兩相鄰時有序無表進行歸併。

(3) 重複執行步驟 (2) 直到歸併成一個長度為 n 的有序表。