数据结构中归并排序的设计与实现Word文件下载.docx
《数据结构中归并排序的设计与实现Word文件下载.docx》由会员分享，可在线阅读，更多相关《数据结构中归并排序的设计与实现Word文件下载.docx（18页珍藏版）》请在冰点文库上搜索。
系主任（或责任教师）签名：
归并排序的设计和实现
摘要:
该程序主要由五个部分组成：
把一组待排的数据信息放在结构体里，2－路归并排序，对数组作一趟归并排序，对数组作归并排序，主函数。
Abstract:
Theprogrammainlyconsistsoffiveparts:
thearowofdata
tobeplacedonstructure,the2-waymergesort,foratriptothearrayMergesort,mergesortonthearrayasthemainfunction.
关键字:
模型化,2－路归并,一趟归并,归并
Keywords:
modeling,2-waymerge,atriptomerge,merge
0.引言
归并排序是一种稳定的内部排序，“归并”的含义是将两个或两个以上的有序表组合成一个新的有序表。
无论是顺序存储结构还是链表存储结构，都可在O（m+n）的时间量级上实现。
利用归并的思想容易实现排序。
2—路归并排序：
假设初始序列含有n个记录，则可看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到不小于n/2整数个长度为2或1的有序子序列；
再两两归并,⋯⋯,如此重复，直至得到一个长度为n的有序序列为止。
1.算法把握
1.1归并排序算法的具体分析咋一看，归并排序时一种“费力不讨好”的排序方法，因为最后一趟始终要对整个序列进行排序，这会使的前几趟的排序似乎是在做无用功，其实不然。
对初始关键字两两分组并进行组内排序后，在下一次处理中，并不是简单地在组容量扩大一倍的基础上重新排序，而是把上一趟已经排好序的两组数组重新合并成一个新的有序组。
这个把两个有序组合并到一个新的有序组的过程要比单独排序快得多。
归并排序的核心操作时合并有序组。
对于最开始的两两分组，也可以看成是两个只含有1个关键字的组进行合并。
1.2除了核心的合并操作外，需要先把序列进行分组，每次组容量减半，直到组内只有一个关键字为止，再对组进行合并，直到所有关键字都属于一组为止。
实际上，分组采用递归的方法更加方便。
2.需求分析
（1）通过建立一个结构体，用来存放数据信息，包括数据的个数，本身记录。
（2）2－路归并排序的算法，实现两两归并。
（3）主函数初始化数据，选择归并排序的方法及打印数据结果。
3.数据结构设计
用结构体存储待排的数据。
#include<
iostream.h>
#defineMAX100/*定义MAX是最大的允许输入数字个数*/
typedefstruct
{
intn;
/*n为文件中的记录个数，n<
MAXNUM*/
intdata[MAX];
}lqlist;
4.算法设计
4.12-路归并排序的非递归算法
//将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n]
voidmerge（RcdTypeSR[],RcdType&
TR[],inti,intm,intn）
for（j=m+1,k=I;
i<
=m&
&
j<
=n;
k++）
{//将SR中记录由小到大的并入TR
if（LQ（SR[i].key,SR[j].key））
TR[k]=SR[i++];
elseTR[k]=SR[j++];
}
if（i<
=m）
TR[k..n]=SR[i..m];
//将剩余的SR[i..m]复制到TR
if（j<
=n）
TR[k..n]=SR[j..n];
}//merge
4.22-路归并排序的递归形式
voidMsort（RcdTypeSR[],RcdType&
TR1[],ints,intt）
//将SR归并排序为TR
if（s==t）
TR1[s]=SR[s];
else
m=（s+t）/2;
//将平分为SR[s..t]和SR[m+1..t]Msort（SR,TR2,s,m）;
//递归的将SR[s..m]归并为有序的TR2[s..m]Msort（SR,TR2,m+1,t）;
//递归地将SR[m+1..t]归并为有序的TR[m+1..t]Merge（TR2,TR1,s,m,t）;
//将TR2[s..m]和TR2[m+1..t]归并到TR1[s..t]
}//mergesort
4.3对顺序表L作归并排序
Voidmergesort（SqList&
L）
Msort（L.r,L.r,1,L.length）;
4.4非递归形式归并算法
voidmerge（intr[],intr1[],intlow,intm,inthigh）
/*r[low]到r[m]和r[m+1]到r[right]是两个有序段*/
inti=low,j=m+1,k=low;
while（i<
=m&
j<
=high）
/*反复复制两个段的第一个记录中较小的*/
if（r[i]<
=r[j]）
r1[k++]=r[i++];
r1[k++]=r[j++];
while（i<
=m）
/*复制第一个段的剩余记录*/
while（j<
=high）
/*复制第二个段的剩余记录*/
4.5对r做一趟归并的算法
voidmergePass（intr[],intr1[],intn,intlength）{
inti=0,j;
/*length为本趟归并的有序子段的长度*/
while（i+2*length-1<
n）
/*归并长length的两个子段*/
merge（r,r1,i,i+length-1,i+2*length-1）;
i+=2*length;
if（i+length-1<
n-1）/*剩下两段，后一段长度小于length*/merge（r,r1,i,i+length-1,n-1）;
else/*将剩下的一段复制到数组r1*/for（j=i;
n;
j++）r1[j]=r[j];
4.6对整个数据进行归并的算法
voidmergeSort（SortObject*p）
intdata[MAXNUM];
intlength=1;
while（length<
p->
n）
/*一趟归并，结果存放在数组record中*/
mergePass（p->
record,record,p->
n,length）;
length*=2;
/*一趟归并，结果存回*/
mergePass（record,p->
record,p->
4.7主程序
main（）{
cout<
<
"
endl;
归并排序的递归和非递归实现
*********************"
lqlistp;
inti=0,z,m,k;
请输入所要比较的数字组，以10000结束：
"
cin>
>
z;
while（z!
=10000&
MAX）{
p.data[i]=z;
i++;
cin>
p.n=i;
排序前的数组是：
for（i=0;
p.n;
i++）
p.data[i]<
;
请选择需要归并排序的方法"
endl
1.选择递归方法。
2.选择非递归方法。
m;
if（m==1）
M（&
p）;
else{if（m==2）mergesort2（&
输入有误。
endl<
排序后的数组：
{/*输出排序前的数组*/
p.data[i]<
请选择服务:
1.选择非递归方法。
2.退出。
k;
if（m==1&
k==1）
/*选择递归方法进行归并排序*/
else{
if（m==2&
mergesort2（&
/*选择非递归方法进行归并排序*/
elseif（k==2）
return0;
{/*输出递归排序后的数组*/cout<
5.程序的实现
5.1完整程序
#defineMAX100
typedefstruct{
voidmerge（inta[],ints1,inte1,ints2,inte2,intb[]）{
intk=s1;
inti=s1;
while（（s1<
=e1）&
（s2<
=e2））
if（a[s1]<
=a[s2]）
{/*将数组a[s1]和数组a[s2]中小的数据暂存到数组b[]中*/b[k]=a[s1];
k++;
s1++;
{/*将数组a[s1]和数组a[s2]中小的数据暂存到数组b[]中*/b[k]=a[s2];
s2++;
while（s1<
=e1）
{/*将第一个数组中剩余的数据暂存到数组b[]中*/
b[k]=a[s1];
while（s2<
=e2）
{/*将第二个数组中剩余的数据存到暂存数组b[]中*/b[k]=a[s2];
k--;
while（k>
=i）
{/*将暂存数组b[]中的数据村回到a[]中*/
a[k]=b[k];
voidmergesort（inta[],inti,intj,intb[]）
intk;
j）{
k=（i+j）/2;
mergesort（a,i,k,b）;
//递归的将a[i..k]归并为有序的b[i..k]mergesort（a,k+1,j,b）;
//递归的将a[k+1..j]归并为有序的b[k+1..j]merge（a,i,k,k+1,j,b）;
//将a[i..k]和TR2[k+1..j]归并到b[s..t]
voidM（lqlist*q）
intc[MAX];
mergesort（q->
data,0,q->
n-1,c）;
voidmerge2（intr[],intr1[],intlow,intm,inthigh）
/*r[low]到r[m]和r[m+1]到r[right]是两个有序段*/
inti=low,j=m+1,k=low;
while（i<
=high）{/*反复复制两个段的第一个记录中的较小的*/if（r[i]<
=r[j]）
r1[k]=r[i];
r1[k]=r[j];
j++;
while（i<
{/*复制第一个段的剩余记录*/
while（j<
=high）
{/*复制第二个段的剩余记录*/r1[k]=r[j];
/*对r做一趟归并，结果放在r1中*/
voidmergepass2（intr[],intr1[],intn,intlength）
{/*length为本趟归并的有序子段的长度*/
inti=0,j;
=n-2*length+1）
{/*剩下两段，后一段长度小于length*/merge2（r,r1,i,i+length-1,i+2*length-1）;
/*归并长length的两个子段*/i+=2*length;
n-length+1）/*剩下两段，后一段长度小于length*/merge2（r,r1,i,i+length-1,n-1）;
else/*将剩下的一段复制到数组r1*/for（j=i;
j++）
r1[j]=r[j];
voidmergesort2（lqlist*p）
intlength=1;
inti;
while（length<
p->
/*一趟归并，结果存在数组record中*/mergepass2（p->
data,data,p->
n,length）;
length*=2;
/*一趟归并，结果存回*/mergepass2（data,p->
data,p->
MAX）
{/*对数组进行循环输入，并以10000结束输入*/p.data[i]=z;
i++）cout<
endl<
i++）{/*输出归并前的数组*/cout<
/*再次进行选择服务（另一种排序方法还是退出）*/if（m==1&
/*将用递归方法进行归并排序*/
else{if（m==2&
/*将用非递归方法进行归并*/
i++）{
5.2程序运行过程说明
该程序的功能是实现归并排序，程序的运行过程中需要实验者输入所要进行归并排序的数字组（最多不能超过MAX个），并且以10000结束，输入数字组后，程序会输出实验者输入的数字组（不包括最后实验者输入的10000），并需要实
验者自己选择需要归并的方法（递归方法或非递归方法），当实验者输入一种归并排序的方法后程序会运用该方法进行归并排序，并输出该方法排序的结果，并继续需要实验者选择进行另一种排序方法还是需要退出，当实验者选择另一种方法时，程序会进行另一种归并排序的方法，并输出排序后的结果，然后程序自动结束。
如果实验者在第二次选择时直接选择退出，程序不会进行另一种归并排序方法，直接结束程序。
5.3程序运行结果
6.归并排序的复杂度分析
递归排序所消耗的时间有两部分组成：
分组时间和合并时间。
给定序列中有n个元素，同时为了方便计算，假设n为2的幂，这样的每次分组，会分成偶数的两部分。
用于合并的时间随着元素数量的增加时线性增长的，这个时间不超过cn（c为某个常数），所以归并算法所消耗的时间为T（n）=2T（n/2）+cn.最后化简得：
T（n）=n+cnlogn.所以最后得出归并排序的时间复杂度是O（nlogn）。
归并排序的最大不足在于它需要与原序列大小相同的辅助空间，而且分组合并后还需要把辅助空间的数据复制回原序列，这会进一步降低算法的速度。
7.设计体会
通过这次实验我也着实又感受了一次编程的乐趣，从中也学到了不少知识。
做程序是一个比较累的工作，特别是当遇到困难时，程序通不过时，真的很令人沮丧。
但是改正一个错误时，那种喜悦心情也很令人期盼，这种心情堪比久旱见甘霖的喜悦。
就是因为有这种令人身心愉悦的可能，我才得以能够整晚不睡来改程序中的不足之处。
编程中有苦有乐，其中的苦乐只有亲身经历才能体会到。
要想做出好的程序，必须做好忍受其间痛苦的准备。
虽然都说“程序＝数据结构＋算法”，但我在学习运用数据结构编程之前，并没能深刻体会到这一点，直到这次课设实践。
我感受最深的一点是：
以前用C、c++编程，只是注重如何编写函数能够完成所需要的功能，似乎没有明确的战术，只是凭单纯的意识和简单的语句来堆砌出一段程序，只要能完成任务就行。
但现在编程感觉完全不同了。
在编写一个程序之前，自己能够综合考虑各种因素，首先选取自己需要的数据结构，是树还是图或是别的什么？
然后选定一种或几种存储结构来具体的决定后面的函数的主要风格。
最后在编写每一个函数之前，可以仔细斟酌比对，挑选出最适合当前状况的算法。
这样，即使在完整的程序还没有写出来之前，自己心中已经有了明确的原图了。
这样无形中就提高了自己编写的程序的质量。
另外，我还体会到深刻理解数据结构的重要性。
只有真正理解这样定义数据类型的好处，才能用好这样一种数据结构。
了解典型数据结构的性质是非常有用的，它往往是编写程序的关键，在每次编程之前也要根据程序的要求来选择合适的数据存储结构，例如线性表的顺序存储还是链式存储，是运用图还是运用树比较好，这些都要在设计程序之前进行认真的思索和权衡。
这次实验中我也出现过一些比较困难的地方。
在对数据进行模型化的时候，只用数组不能足以获取数据的信息，必须建立一个结构体。
后来在同学的指点下，意识到自己的错误。
这次实验的另一个感悟就是平时生活和学习中一定要多多动手实践，只有在实践过程中才会发现自己的不足之处，发现问题的所在，并一步步寻求解决问题的方法，正是在发现问题到解决问题的这一过程，解决问题的思路就会慢慢的打开，也正是这一过程使自己慢慢的得到锻炼和发展，知识在这一过程中也得到积蓄。
总之，我会继续我的兴趣编写程序的，相信在越来越多的尝试之后，自己会不断进步不断提高的。
8.结束语
本程序运用递归和非递归两种方法实现了数据的归并排序，主要是2－路归并排序的过程，程序运行简单易行，可操作性可靠，结果明了。
参考文献
[1]周桂红，王超，常淑慧数.《数据结构》，北京邮电大学出版社2010年9月
[2]严蔚敏，吴伟名.《据结构》，清华大学出版社，2001年1月
[3]赵仲孟，张蓓.《数据结构》，西北工业大学出版社，2001年9月
[4]郑莉，董渊，张瑞丰.《C++语言程序设计》。
清华大学出版社，2003年1月
本科生课程设计成绩评定表
班级：
姓名：
学号：
序号
评分项目
满分
实得分
1
学习态度认真、遵守纪律
10
2
设计分析合理性
3
设计方案正确性、可行性、创造性
20
4
设计结果正确性
40
5
设计报告的规范性
6
设计验收
总得分/等级
评语：
注：
最终成绩以五级分制记。
优（90-100分）、良（80-89分）、中（70-79分）、及格（60-69分）、60分以下为不及格
升级会员 