首页 / 算法 / 二路归并排序算法

二路归并排序算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了二路归并排序算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1409字，纯文字阅读大概需要3分钟。

内容图文

      归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
      归并过程为：比较a[i]和a[j]的大小，若a[i]≤a[j]，则将第一个有序表中的元素a[i]复制到r[k]中，并令i和k分别加上1；否则将第二个有序表中的元素a[j]复制到r[k]中，并令j和k分别加上1，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。归并排序的算法我们通常用递归实现，先把待排序区间[s,t]以中点二分，接着把左边子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。

 

图解：

技术分享

 

实现代码：

技术分享 技术分享 
                 1 #include <fstream>
 2 #include <iostream>
 3 #include <cstdio>
 4 5usingnamespace std;
 6 7constint N=100;
 8int n,r[N],r1[N];
 9void merge(int s,int m,int t);//将有序列[s,m]与[m+1,t]合并10void merge_sort(int s,int t);//将r[s,t]归并排序为r1[s,t]1112int main()
13{
14//freopen("D:\\input.in","r",stdin);
15//freopen("D:\\output.out","w",stdout);16     scanf("%d",&n);
17for(int i=1;i<=n;i++)
18         scanf("%d",&r[i]);
19     merge_sort(1,n);
20for(int i=1;i<n;i++)
21         printf("%d ",r1[i]);
22     printf("%d\n",r1[n]);
23return0;
24}
25void merge(int s,int m,int t)
26{
27int i=s,j=m+1,k=s;
28while(i<=m&&j<=t)
29    {
30if(r[i]<r[j])   r1[k++]=r[i++];
31else    r1[k++]=r[j++];
32    }
33while(i<=m) r1[k++]=r[i++];
34while(j<=t) r1[k++]=r[j++];
35for(int e=s;e<=t;e++)
36         r[e]=r1[e];
37}
38void merge_sort(int s,int t)
39{
40if(s==t)    r1[s]=r[s];
41else42    {
43int m=(s+t)/2;
44        merge_sort(s,m);
45         merge_sort(m+1,t);
46        merge(s,m,t);
47    }
48 }
View Code

 

原文：http://www.cnblogs.com/jiu0821/p/4231331.html

内容总结

以上是互联网集市为您收集整理的二路归并排序算法全部内容，希望文章能够帮你解决二路归并排序算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1117503.html

来源：【匿名】