【C语言程序设计】C语言的归并排序算法！

冷不防 2022-11-06 11:59 190阅读 0赞

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

### 实现过程： ###

**(1) **自定义函数 merge()，实现一次归并排序。

**(2)** 自定义函数 merge\_sort()，实现归并排序。

### 程序代码如下： ###

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

![4cfdceac58eb45a5d88ee280e51493ae.gif][]

不管你是转行也好，初学也罢，进阶也可，如果你想学编程，进阶程序员~

【**值得关注**】我的 **[编程学习交流俱乐部][Link 1]！【点击进入】**

![1b3c3f17fa7bc9a1e41d2f94017b040b.png][]

[4cfdceac58eb45a5d88ee280e51493ae.gif]: /images/20221023/f8ddf87690a94694a53162120fb7efb0.png
[Link 1]: https://jq.qq.com/?_wv=1027&k=teZNipK1
[1b3c3f17fa7bc9a1e41d2f94017b040b.png]: /images/20221023/ad85d082e27940878ff3499904d4cc2e.png