C语言编程实例：10、归并排序算法

用归并排序法对一组数据由小到大进行排序，数据分别为 695、458、362、789、12、 15、163、23、2、986。

算法表述：

归并排序的基本原理是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。其实通俗来说，对于一个数来说自身是有序的，然后每次选取两个数使之自身有序，然后每次选取四个数使之自身有序，以后以二倍增长选择，进行排序。将若将两有个有序表合成一个有序表，成为二路归并。（具体可以依据下图进行分析）

算法执行过程分析：

例如：15、2、35、6、23、11、5
说明：其中s1,s2,e1,e2 分别表示两个归并段的首尾位置，brr[]为辅助数组，arr[]为存储结果的数组。
具体步骤：

实现过程：
(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(void) {
    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
排序后的顺序是：
    8   12   15   23  163  362  458  695  789  986

** 方法二 **

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

void Merge(int *arr,int len,int gap)
{
    int *brr = (int *)malloc(sizeof(int) * len);  //动态开辟辅助数组
    assert(brr != NULL);
    int i = 0;           //brr的下标
    int start1 = 0;
    int end1 = start1+gap-1;
    int start2 = end1+1;
    int end2 = start2 + gap - 1 < len - 1 ? start2 + gap - 1 : len - 1 ;     //当有两个归并段的时候
    while(start2 < len)
    {
        //当两个归并段还没有比较完的时候
        while(start1 <= end1 && start2 <= end2)
        {
            if(arr[start1] <= arr[start2])
            {
                brr[i++] = arr[start1++];
            }
            else
            {
                brr[i++] = arr[start2++];
            }
        }
        while(start1 <= end1)     //如果是第二个归并段比较完了，则将第一个归并段中的数放在brr[]
        {
            brr[i++] = arr[start1++];
        }
        while(start2 <= end2)  //如果是第一个归并段比较完了，则将第二个归并段中的数放在brr[]
        {
            brr[i++] = arr[start2++];
        }
        //找两个新的归并段
        start1 = end2+1;
        end1 = start1+gap-1;
        start2 = end1+1;
        end2 = start2+gap-1 < len-1?start2+gap-1:len-1;
    }
    while(start1 < len)  //如果在最后不存在第二个归并段，则将第一个归并段中的数放在brr[]
    {
        brr[i++] = arr[start1++];
    }
    for(int i = 0;i < len;i++)    //数值拷贝
    {
        arr[i] = brr[i];
    }
}
void MergeSort(int *arr,int len)
{
    for(int i = 1;i < len;i *= 2)   //i表示分组数，分组形式为1 2 4 8....
    {
        Merge(arr,len,i);
    }
}

int main(void) {
    int a[11];
    int i;
    printf("请输入10个数：\n");
    for (i = 1; i <= 10; i++)
        scanf("%d", &a[i]);    //从键盘中输入10个数
    MergeSort(a,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
排序后的顺序是：
    8   12   15   23  163  362  458  695  789  986

技术要点：

归并是将两个或多个存序记录序列合并成一个有序序列。归并方法有多种，一次对两个有序记录序列进行归并，称为路归并排序，也有三路归并排序及多路归并排序。本实例是二路归并排序，基本方法如下：

(1) 将 n 个记录看成是 n 个长度为 1 的有序子表。

(2) 将两两相邻时有序无表进行归并。

(3) 重复执行步骤 (2) 直到归并成一个长度为 n 的有序表。

Crazer的自留地