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 的有序表。