归并排序(Merge Sort)

基本思想:

归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

归并排序示例:

合并方法:

若i>m 或j>n,转⑷ //其中一个子表已合并完,比较选取结束

  • //选取r[i]和r[j]较小的存入辅助数组rf 如果r[i]<r[j],rf[k]=r[i]; i++; k++; 转⑵ 否则,rf[k]=r[j]; j++; k++; 转⑵
  • //将尚未处理完的子表中元素存入rf 如果i<=m,将r[i…m]存入rf[k…n] //前一子表非空 如果j<=n ,  将r[j…n] 存入rf[k…n] //后一子表非空
  • 合并结束。
//将r[i…m]和r[m +1 …n]归并到辅助数组rf[i…n]
void Merge(ElemType *r,ElemType *rf, int i, int m, int n)
{
	int j,k;
	for(j=m+1,k=i; i<=m && j <=n ; ++k){
		if(r[j] < r[i]) rf[k] = r[j++];
		else rf[k] = r[i++];
	}
	while(i <= m)  rf[k++] = r[i++];
	while(j <= n)  rf[k++] = r[j++];
}

归并的迭代算法

1 个元素的表总是有序的。所以对n 个元素的待排序列,每个元素可看成1 个有序子表。对子表两两合并生成n/2个子表,所得子表除最后一个子表长度可能为1 外,其余子表长度均为2。再进行两两合并,直到生成n 个元素按关键码有序的表。

void print(int a[], int n){
	for(int j= 0; j<n; j++){
		cout<<a[j] <<"  ";
	}
	cout<<endl;
}

//将r[i…m]和r[m +1 …n]归并到辅助数组rf[i…n]
void Merge(ElemType *r,ElemType *rf, int i, int m, int n)
{
	int j,k;
	for(j=m+1,k=i; i<=m && j <=n ; ++k){
		if(r[j] < r[i]) rf[k] = r[j++];
		else rf[k] = r[i++];
	}
	while(i <= m)  rf[k++] = r[i++];
	while(j <= n)  rf[k++] = r[j++];
	print(rf,n+1);
}

void MergeSort(ElemType *r, ElemType *rf, int lenght)
{ 
	int len = 1;
	ElemType *q = r ;
	ElemType *tmp ;
	while(len < lenght) {
		int s = len;
		len = 2 * s ;
		int i = 0;
		while(i+ len <lenght){
			Merge(q, rf,  i, i+ s-1, i+ len-1 ); //对等长的两个子表合并
			i = i+ len;
		}
		if(i + s < lenght){
			Merge(q, rf,  i, i+ s -1, lenght -1); //对不等长的两个子表合并
		}
		tmp = q; q = rf; rf = tmp; //交换q,rf,以保证下一趟归并时,仍从q 归并到rf
	}
}


int main(){
	int a[10] = {3,1,5,7,2,4,9,6,10,8};
	int b[10];
	MergeSort(a, b, 10);
	print(b,10);
	cout<<"结果:";
	print(a,10);

}
两路归并的递归算法
void MSort(ElemType *r, ElemType *rf,int s, int t)  
2.{   
3.    ElemType *rf2;  
4.    if(s==t) r[s] = rf[s];  
5.    else  
6.    {   
7.        int m=(s+t)/2;          /*平分*p 表*/  
8.        MSort(r, rf2, s, m);        /*递归地将p[s…m]归并为有序的p2[s…m]*/  
9.        MSort(r, rf2, m+1, t);      /*递归地将p[m+1…t]归并为有序的p2[m+1…t]*/  
10.        Merge(rf2, rf, s, m+1,t);   /*将p2[s…m]和p2[m+1…t]归并到p1[s…t]*/  
11.    }  
12.}  
13.void MergeSort_recursive(ElemType *r, ElemType *rf, int n)  
14.{   /*对顺序表*p 作归并排序*/  
15.    MSort(r, rf,0, n-1);  
16.}  

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏禁心尽力

Set容器--HashSet集合

Set容器特点: ①   Set容器是一个不包含重复元素的Collection,并且最多包含一个null元素,它和List容器相反,Set容器不能保证其元素的顺...

23750
来自专栏XAI

Java数组操作的10大方法

0、定义一个Java数组 String[] aArray = new String[5]; String[] bArray = {"a","b","c", "d...

24660
来自专栏互联网大杂烩

二分查找

在对线性表的操作中,经常需要查找某一个元素在线性表中的位置。此问题的输入是待查元素x和线性表L,输出为x在L中的位置或者x不在L中的信息。

8230
来自专栏Java帮帮-微信公众号-技术文章全总结

第十九天 集合-Map接口容器工具类集合框架总结【悟空教程】

Map集合的特点,如是否可重复,是否有序仅作用在键上,如HashMap集合的键不得重复,值可以重复。

24730
来自专栏于晓飞的专栏

读 Java Arrays 源码 笔记

Arrays.java是Java中用来操作数组的类。使用这个工具类可以减少平常很多的工作量。了解其实现,可以避免一些错误的用法。

11320
来自专栏LanceToBigData

JavaSE(八)之集合练习一

前面把Collection家族给学习完毕了,接下来我们通过几个练习来巩固前面的知识。   一、产生10个1-20之间的随机数要求随机数不能重复 import j...

21190
来自专栏云霄雨霁

字符串排序----低位优先的字符串排序

32500
来自专栏武培轩的专栏

剑指Offer-二进制中1的个数

package Other; /** * 二进制中1的个数 * 输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。 */ public c...

26640
来自专栏mySoul

​单链表 C++

18820
来自专栏待你如初见

Day10

16020

扫码关注云+社区

领取腾讯云代金券