合并排序:把两个或多个有序序列合并为一个有序的序列。
例子:
合并503,703,765和087,512,677,得到087,503,512,677,703,765。每次比较两个序列最小的数,输出最小的,不断重复这个过程。
如:
<!--[if gte vml 1]><v:shapetype id="_x0000_t75"
coordsize="21600,21600" o:spt="75" o:preferrelative="t" path="m@4@5l@4@11@9@11@9@5xe"
filled="f" stroked="f">
<v:stroke joinstyle="miter" />
<v:formulas>
<v:f eqn="if lineDrawn pixelLineWidth 0" />
<v:f eqn="sum @0 1 0" />
<v:f eqn="sum 0 0 @1" />
<v:f eqn="prod @2 1 2" />
<v:f eqn="prod @3 21600 pixelWidth" />
<v:f eqn="prod @3 21600 pixelHeight" />
<v:f eqn="sum @0 0 1" />
<v:f eqn="prod @6 1 2" />
<v:f eqn="prod @7 21600 pixelWidth" />
<v:f eqn="sum @8 21600 0" />
<v:f eqn="prod @7 21600 pixelHeight" />
<v:f eqn="sum @10 21600 0" />
</v:formulas>
<v:path o:extrusionok="f" gradientshapeok="t" o:connecttype="rect" />
<o:lock v:ext="edit" aspectratio="t" />
</v:shapetype><v:shape id="图片_x0020_4" o:spid="_x0000_i1029" type="#_x0000_t75"
style='width:106.5pt;height:36.75pt;visibility:visible;mso-wrap-style:square'>
<v:imagedata src="file:///C:\DOCUME~1\ADMINI~1\LOCALS~1\Temp\msohtmlclip1\01\clip_image001.png"
o:title="" />
</v:shape><![endif]--><!--[if !vml]--><!--[endif]-->
得到:
<!--[if gte vml 1]><v:shape
id="图片_x0020_7" o:spid="_x0000_i1028" type="#_x0000_t75" style='width:130.5pt;
height:45pt;visibility:visible;mso-wrap-style:square'>
<v:imagedata src="file:///C:\DOCUME~1\ADMINI~1\LOCALS~1\Temp\msohtmlclip1\01\clip_image003.png"
o:title="" />
</v:shape><![endif]--><!--[if !vml]--><!--[endif]-->
然后:
<!--[if gte vml 1]><v:shape
id="图片_x0020_10" o:spid="_x0000_i1027" type="#_x0000_t75" style='width:141.75pt;
height:30pt;visibility:visible;mso-wrap-style:square'>
<v:imagedata src="file:///C:\DOCUME~1\ADMINI~1\LOCALS~1\Temp\msohtmlclip1\01\clip_image005.png"
o:title="" />
</v:shape><![endif]--><!--[if !vml]--><!--[endif]-->
接着:
<!--[if gte vml 1]><v:shape
id="图片_x0020_13" o:spid="_x0000_i1026" type="#_x0000_t75" style='width:162.75pt;
height:29.25pt;visibility:visible;mso-wrap-style:square'>
<v:imagedata src="file:///C:\DOCUME~1\ADMINI~1\LOCALS~1\Temp\msohtmlclip1\01\clip_image007.png"
o:title="" />
</v:shape><![endif]--><!--[if !vml]--><!--[endif]-->
直到一个序列被取尽。
流程图,如下:
<!--[if gte vml 1]><v:shape
id="图片_x0020_1" o:spid="_x0000_i1025" type="#_x0000_t75" style='width:272.25pt;
height:159.75pt;visibility:visible;mso-wrap-style:square'>
<v:imagedata src="file:///C:\DOCUME~1\ADMINI~1\LOCALS~1\Temp\msohtmlclip1\01\clip_image009.png"
o:title="" />
</v:shape><![endif]--><!--[if !vml]--><!--[endif]-->
代码如下:
private void Merge(int seq1[],int start1,int end1,int[]seq2,int start2,int end2 ){
int [] mergeSeq=new int [end1+end2-start1-start2];
int i=0;
while(start1<=end1||start2<=end1){
if(start1>end1||seq1[start1]>seq2[start2]){
mergeSeq[i]=seq2[start2];
start2++;
i++;
}
else if(start2>end2 ||seq1[start1]<=seq2[start2]){
mergeSeq[i]=seq1[start1];
mergeSeq[i]=seq1[start1];
start1++;
i++;
}
}
}
归并排序:采用分治法(Divide and Conquer)和合并排序的一种排序算法;
基本思想:把序列R[start…end]划分为R[start…middle]和R[middle…end],对R[start…middle]和R[middle…end]分别用合并排序,直到被划分的序列为只包含一个元素为止。再对R[start…middle]和R[middle…end]进行合并排序。
实例:
数组A有7个数据,分别是: 49 38 65
97 76 13 27,那么采用归并排序算法的操作过程如图7所示:
初始值
[49] [38] [65] [97]
[76] [13] [27]
看成由长度为1的7个子序列组成
第一次合并之后
[38 49] [65
97] [13 76] [27]
看成由长度为1或2的4个子序列组成
第二次合并之后
[38 49
65 97] [13
27 76]
看成由长度为4或3的2个子序列组成
第三次合并之后
[13 27
38 49
65 76 97]
代码实现:
void Merge(SeqList
R,int low,int m,int high)
{//将两个有序的子文件R[low..m)和R[m+1..high]归并成一个有序的
//子文件R[low..high]
int i=low,j=m+1,p=0; //置初始值
RecType *R1; //R1是局部向量,若p定义为此类型指针速度更快
R1=(ReeType *)malloc((high-low+1)*sizeof(RecType));
if(! R1) //申请空间失败
Error("Insufficient memory
available!");
while(i<=m&&j<=high) //两子文件非空时取其小者输出到R1[p]上
R1[p++]=(R[i].key<=R[j].key)?R[i++]:R[j++];
while(i<=m) //若第1个子文件非空,则复制剩余记录到R1中
R1[p++]=R[i++];
while(j<=high) //若第2个子文件非空,则复制剩余记录到R1中
R1[p++]=R[j++];
for(p=0,i=low;i<=high;p++,i++)
R[i]=R1[p];//归并完成后将结果复制回R[low..high]
} //Merge
分享到:
相关推荐
作业24-归并排序与基数排序.docx 作业24-归并排序与基数排序.docx ...作业24-归并排序与基数排序.docx作业24-归并排序与基数排序.docx作业24-归并排序与基数排序.docx作业24-归并排序与基数排序.docx
这是个算法设计,比较简单,但是可以实现.采用分治策略进行归并排序.
算法设计,给出归并排序的C++实现代码,并利用给随机数方式求运行时间
算法-理论基础- 排序- 归并排序(包含源程序).rar
最快的排序算法 谁才是最强的排序算法:快速排序-归并排序-堆排序,排序算法数据结构
归并排序,排序等算法,数据结构,快速排序,链表排序归并排序,排序等算法,数据结构,快速排序,链表排序
算法设计实验报告,包括:快速排序和归并排序两种算法各自的基本思想、时间复杂度分析,C++实现代码,两种算法运行时间的比较,运行截图,实验心得。
算法的实现----归并排序 数据结构中学过的 编起耍哈哈
15-归并排序.cpp
VC++多线程实现三种排序算法比较----冒泡排序、快速排序、归并排序,很有意思,可以下载看看!
本册主要讨论生成所有树,这个主题与《计算机程序设计艺术》前3卷有着令人吃惊的紧密联系。Knuth在本册中全面地讨论了这个著名的主题,提供了124个新的练习,继续为程序设计打下坚实的基础。同时,本册还论述了组合...
8.12-8.19_冒泡_选择_插入_希尔_快速_归并_基数_堆排序_排序算法Swift代码及UI演示
本册主要讨论生成所有树,这个主题与《计算机程序设计艺术》前3卷有着令人吃惊的紧密联系。Knuth在本册中全面地讨论了这个著名的主题,提供了124个新的练习,继续为程序设计打下坚实的基础。同时,本册还论述了组合...
详解Java常用排序算法-归并排序
该代码是数据结构或算法中的归并排序法,可以使2个不同长度的有序数组合并,入门级分享
排序-6-二路归并.cpp
1.划分:将待排序序列P1,P2,.......Pn划分成两个长度相等的子序列P1,P2,....求解子问题:分别对这个子序列进行归并排序,得到两个有序子序列.(递归实现和非递归实现) 3.合并:将这两个有序子序列合并成一个有序序列.
python 归并排序算法 归并排序是一种基于分治思想的排序算法,它将待排序的序列分成若干个子序列,每个子序列都是有序的,然后再将这些有序的子序列合并成一个有序的序列。归并排序的时间复杂度为O(nlogn),是一种...
Java代码-排序-直接插入排序、希尔排序、直接选择排序、冒泡排序、堆排序、快速排序、归并排序中部分排序以及算法-贪心法,大家可以将源码下载下来进行学习,附带着注释和解释,有不理解的可以找博主一起探讨,共同...