数据结构课程设计二路归并排序说明书

1、前 言1.1排序的重要性生活中，无时不刻不充满这排序，比如：班级同学的成绩排名问题，公司产值高低的问题等等，解决这些问题的过程中，都涉及到了一个数据结构的构造思想过程。数据结构中的排序，也有很多种，如：插入排序、交换排序、选择排序等等，此时我们就要注意选择具有优解的算法，将一个数据元素（或记录）的任意序列，重新排列成一个有序的排列，便于我们查找。假设含有n个记录的序列为R1,R2,Rn,其相应的关键字序列为K1,K2,Kn需确定1，2n的一种排序P1,P2Pn,使其相应的关键字满足如下的非递减的关系：Kp1Kp2Kpn,即按关键字Rp1,Rp2,Rpn有序的排列，这样的一种操作称为排序。一般情

2、况下，排序又分为内部排序和外部排序。而在内部排序中又含有很多排序方法，就其全面性能而言，很难提出一种被认为是最好的方法，因为每一种方法都有它的优缺点，适合在不同的环境下使用。我们学习的排序有:直接插入排序、折半插入排序、希尔排序、快速排序、基数排序、归并排序等。本次课题研究中，我主要进行了二路归并排序的研究和学习。1.2设计的背景和意义排序是计算机领域的一类非常重要的问题，计算机在出来数据的过程中，有25%的时间花在了排序上，有许多的计算机设备，排序用去计算机处理数据时间的一半以上，这对于提高计算机的运行速度有一定的影响。此时排序算法的高效率显得尤为重要。在排序算法汇中，归并排序（Mergin

3、g sort）是与插入排序、交换排序、选择排序不同的另一类排序方法。归并的含义是将两个或两个以上的有序表组合成一个新的有序表。归并排序可分为多路归并排序，两路归并排序，既可用于内排序，也可以用于外排序。这里仅对内排序的两路归并排序进行讨论。而我们这里所探究学习的二路归并排序，设计思路更加清晰、明了，程序本身也不像堆结构那样复杂，同时时间复杂度仅为0(N)，同时在处理大规模归并排序的时候，排序速度也明显优于冒泡法等一些排序算法，提高排序算法的效率。正 文2.1设计内容设计一个利用二路归并算法实现的排序算法，针对输入的一组无序的数，利用栈或者数组机芯存储，然后进行数据的两两分组、比较，构造新的栈或

4、者数组，依次类推，直到得到一个有序数组或者栈，最后输出有序数据，得到有序数据。2.2设计要求假设初始序列含有n 个数据（n是已经确定的数据个数），首先把n 个记录看成n个长度为1的有序序列，进行两两归并，得到n/2个长度为2的有序序列，再两两归并直到所有记录归并成一个长度为n的有序序列为止。2.3设计思想对于任意一组数据，先利用栈或者数组将数据存储起来，其中，我们会用到线性表的顺序存储和链式存储两种存储方法。然后对存储的数据进行查找和筛选、排序，在出栈的过程中，同时对所取数据进行分组、排列，再次构造新的存储栈或者数组，依次类推，直到得到一个有序的数据时，执行出栈命令，输出最后的排序结果。 为了

5、更清晰地说清楚这里的思想，大家来看图1，我们将本是无序的数组序列16,7,13,10,9,15,3,2,5,8,12,1,11,4,6,14，通过两两合并排序后，再合并，最终获得了一个有序的数组。仔细观察它的形状，很像一棵倒置的完全二叉树，利用两两的比较，一次进行递归排序，最终得到一个从小到大的有序序列。图 12.4 主要模块主要模块式有四个阶段，依次是：输入一组无序的数列，用数据结构或者链式结构进行存储，然后进行查找、分组，进行最后的归并排序。（如图2所示）输入一组无序的数据存 储查 找，分 组归并排序图 22.5排序设计内容此次操作要用到顺序结构的存储，顺序表的查找，以及二路归并排序。 顺

6、序表的存储首先利用顺序存储结构，把所有学生的成绩按每个班，每个学校，每个县，每个市，用线性表的顺序存储机构分别存储起来。顺序表的基本操作如下：Initlist(&L) 操作结果：构造一个空的线性表L;Destroylist(&L) 操作结果：销毁线性表L;Clearlist(&lL) 操作结果：将L重置为空表（线性表L已经存在）；Iiselength(L) 操作结果:返回L中数据元素的个数；GetElem(L,I,&e) 操作结果：用e返回L中第i个数据元素的值； 顺序表的查找Int Search-Sep(SSTable ST , KeyType key)/在顺

7、序表ST中顺序查找其关键字等于Key的数据元素。若找到，则函数值为该元素在表中的位置，否则为0ST.elem0.Key=key; 哨兵；For(i=ST.length; !EQ(ST.elemi.key.key) 从后往前找；Return I; 找不到是i为0；/Search-Sep 归并排序代码：/* 对顺序表L作归并排序 */void MergeSort(SqList *L)   MSort(L->r,L->r,1,L->length);2.6算法设计本次设计主要用用到下面的算法：归并排序算法的实现&#

8、160;     递归算法就是对n个数据进行两两归并，得到n/2个长度为2的有序序列，再两两归并直到所有记录归并成一个长度为n的有序序列为止。递归算法实现中，最重要的就是对n/2进行很多次的归并递归排序算法的设计，调用函数MSort中采用了递归的算法思想，用较简短的语句，实现了多次递归排序。假设现在要对数组50,10,90,30,70,40,80,60,20进行排序，L.length=9，一下就是MSort主要代码及实现过程。/* 将SRs.t归并排序为TR1s.t */1 void MSort(int 

9、SR,int TR1,int s, int t)2 3 int m;4 int TR2MAXSIZE+1;5 if(s=t)6 TR1s=SRs;7 Else8 9 m=(s+t)/2;   /* 将SRs.t平分为SRs.m和SRm+1.t */10 MSort(SR,TR2,s,m); /* 递归地将SRs.m归并为有序的TR2s.m */11 MSort(SR,TR2,m+1,t); /* 递归地将SRm+1.t归并为有

10、序TR2m+1.t */12 Merge(TR2,TR1,s,m,t); /* 将TR2s.m和TR2m+1.t归并到TR1s.t */13 14 1) MSort被调用时，SR与TR1都是50,10,90,30,70,40,80,60,20，s=1，t=9，最终我们的目的就是要将TR1中的数组排好顺序。2) 第5行，显然s不等于t，执行第813行语句块。3) 第9行，m=(1+9)/2=5。m就是序列的正中间下标4) 此时第10行，调用“MSort(SR,TR2,1,5);”的目标就是将数组SR中的第15的关键字归并到有序的TR2（调用前TR2为空数组

11、），第11行，调用“MSort(SR,TR2,6,9);”的目标就是将数组SR中的第69的关键字归并到有序的TR2。也就是说，在调用这两句代码之前，代码已经准备将数组分成两组。如图4所示：图45) 第12行，函数Merge的代码细节一会再讲，调用“Merge(TR2,TR1,1,5,9);”的目标其实就是将第10和11行代码获得的数组TR2（注意它是下标为15和69的关键字分别有序）归并为TR1，此时相当于整个排序就已经完成了。如图5所示： 图56) 第10行递归调用进去后，s=1，t=5，m=(1+5)/2=3。此时相当于将5个记录再为三个和两个。继续递归进去，直到细分为一个记录填

12、入TR2，此时s与t相等，递归返回，如图6的左图。每次递归返回后都会执行当前递归函数的第12行，将TR2归并到TR1中。如图6的右图。最终使得当前序列有序。图67) 同样的第11行也是类似方式，如图7。 图78) 此时也就是刚才所讲的最后一次执行第12行代码，将10,30,50,70,90与20,40,60,80归并为最终有序的序列。以下是对此段递归算法程序的图示：(如图8) 图8归并排序算法的整合在经过每个新的排序片段以后，程序产生新的数组，如何让新的数组依然按照一定顺序进行排序,即将SRi.m和SRm+1.n归并为有序的TRi.n，此时就要进行Merge()函数的调用。

13、一下就是Merge()函数实现的详细过程： /* 将有序的SRi.m和SRm+1.n归并为有序的TRi.n */1 void Merge(int SR,int TR,int i,int m,int n)2 3 int j,k,l;4 4  for(j=m+1,k=i;i<=m && j<=n;k+) /* 将SR中记录由小到大归并入TR */5  6 

14、;  if (SRi<SRj)7    TRk=SRi+;8 else9 9    TRk=SRj+;10  11  if(i<=m)12  13   for(l=0;l<=m-i;l+)14    TRk+l=SRi+l;  /* 将剩余的SRi.m复制到TR */15  16&

15、#160; if(j<=n)17 18 18   for(l=0;l<=n-j;l+)19    TRk+l=SRj+l;  /* 将剩余的SRj.n复制到TR */20  21  1) 假设我们此时调用的Merge就是将10,30,50,70,90与20,40,60,80归并为最终有序的序列，因此数组SR为10,30,50,70,90,20,40,60,80，i=1，m=5，n=9。2) 第4行，for

16、循环，j由m+1=6开始到9，i由1开始到5，k由1开始每次加1，k值用于目标数组TR的下标。3) 第6行，SRi=SR1=10，SRj= SR6=20，SRi<SRj，执行第7行，TRk=TR1=10，并且i+。如图9。图94) 再次循环，k+得到k=2，SRi=SR2=30，SRj= SR6=20，SRi>SRj，执行第9行，TRk=TR2=20，并且j+，如图10。图105) 再次循环，k+得到k=3，SRi=SR2=30，SRj= SR7=40，SRi<SRj，执行第7行，TRk=TR3=30，并且i+，如图11。图116) 接

17、下来完全相同的操作，一直到j+后，j=10，大于9退出循环。如图12。 图127) 第1120行的代码，其实就将归并剩下的数组数据，移动到TR的后面。当前k=9，i=m=5，执行第1320行代码，for循环l=0，TRk+l=SRi+l=90。大功告成。2.7 程序运行说明首先输入需要进行二路归并排序的个数N，然后输入需要进行二路归并排序的数据，期间有空格或者是回车均可，最后输出结果。2.8 程序运行截图输入本是无序的数组序列16,7,13,10,9,15,3,2,5,8,12,1,11,4,6,14，运行结果如下（图13）：图13小 结通过本次课程设计，我对于数据的存储结

18、构，线性表的查找以及归并排序有了更近一步的了解。开始对很多东西感到莫名其妙，很难理解各个简单游戏和系统的管理及编程，总觉得他们是很抽象的东西，但是在学习了数据结构与算法这门课程之后，我慢慢地体会到了其中的奥妙，首先要捕捉他有哪些具体化、数字化的信息，这也就说明了想要把生活中的信息转化到计算机中必须用数字来完整的构成一个信息库。当然对于此设计也存在很多的缺点。比如说，对于线性表的顺序存储结构，虽然，可以随机存储任意元素，但是插入和删除元素是需要移动大量的元素，而且，在计算机内需要预先分配最大的存储空间;而在顺序表的查找过程中，如果数据元素过多，对于顺序查找很不方便。计算机中实现这么一个很简单的想

19、法就需要涉及到很多专业知识，为了完成设计，在前期工作中，基本都是以学习C语言为主，所以浪费了很多时间，但是我在这次课设中也学到了很多。把我在书本上难以理解的东西都给解决了，同时还锻炼了我的动手操作能力。我很感激这次的课题设计。参考文献1严蔚敏 吴伟民 著， 数据结构（C语言版），清华大学出版社，2007.42李春葆 著，数据结构教程，清华大学出版社，2005.13 美Deitel,H.M.，美Deitel,P.J.著, C程序设计经典教程，清华大学出版社，20064 孙鑫.VC+深入详解.北京：电子工业出版社.20075钱能.C+程序设计教程.北京：清华大学出版社.2009附 录#includ

20、e <stdio.h>void merge( int a , int b , int l , int m , int h )/将有序的al.m和bm+1.h合并成有序表bl.hint i,j,k;i=l;j=m+1;k=l;/将两个有序表中较小的放入b中while( i<=m && j<=h) if( ai < aj)bk+=ai+;elsebk+=aj+;while( i<=m )bk+=ai+;while( j<=h )bk+=aj+;for(int q=l; q<=h; q+)/必要操作，有的课本会遗漏此步，使a与b相等aq=bq;void merge_sort(int