数据结构课程设计排序算法演示系统22788.pdf

《数据结构课程设计排序算法演示系统22788.pdf》由会员分享，可在线阅读，更多相关《数据结构课程设计排序算法演示系统22788.pdf（34页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、各专业全套优秀毕业设计图纸 计算机学院 数据结构课程设计 题 目：数据结构排序算法演示系统 班 级：姓 名：学 号：同组人姓名：起 迄 日 期:课程设计地点:指导教师：评阅意见：成绩评定：评阅人：日期：完成日期：2014 年 12 月 目录 一、课程设计的目的.1 二、设计内容和要求.1 三、数据采取的结构.1 四、功能模块详细设计.1 4.1 详细设计思想.2 4.1.1 冒泡排序.5 4.1.2 快速排序.7 4.1.3 直接插入排序.9 4.1.4 希尔排序.10 4.1.5 直接选择排序.12 4.1.6 堆排序.14 4.1.7 归并排序.17 五、总结或心得体会.19 六、参考文献

2、.20 七、附录.20 -1-一.设计目的 随着计算机技术的发展，各种排序算法不断的被提出。排序算法在计算机科学中有非常重要的意义，且应用很广泛。在以后的发展中排序对我们的学习和生活的影响会逐渐增大，很有必要学习排序知识。此次课程设计一方面使自己掌握排序的知识，另一方面锻炼一下团队合作开发系统的能力。二.设计内容和要求 功能要求：(1)界面友好，易与操作。可采用菜单或其它人机对话方式进行选择。(2)实现各种内部排序。包括直接插入排序，冒泡排序，直接选择排序，希尔排序，快速排序，堆排序，归并排序。(3)待排序的元素的关键字为整数或（字符）。可用随机数据和用户输入数据作测试比较。比较的指标为有关键

3、字参加的比较次数和关键字的移动次数(关键字交换以 3 次计)。（1）演示程序以人机对话的形式进行。每次测试完毕显示各种比较指标值的列表，以便比较各种排序的优劣。三.本设计所采用的数据结构 typedef struct int key;RecType;四.功能模块详细设计 希尔排序 排序算法演示系统 冒泡排序 归并排序 快速排序 直接插入排序 直接选择排序 堆排序 -2-4.1 详细设计思想 主函数：#include#include#include#define L 8 /排序元素个数#define FALSE 0#define TRUE 1 typedef struct int key;Rec

4、Type;RecType RL;int num;int sum;int sun;/定义排序趟数的全局变量 /系统主界面/主函数 int main()RecType S100;int i,k;char ch1,ch2,q;printf(ntt*排序算法演示系统*nntt 请输入%d 个待排序的数据：n,L);for(i=1;i=L;i+)printf(tt 请输入第%dth 数据:,i);scanf(%d,&Si.key);getchar();ch1=y;while(ch1=y)printf(ntt 菜 单 n);printf(ntt*n);printf(ntt*1-更新排序数据*2-直接插入排

5、序 n);printf(ntt*3-希 尔 排 序*4-冒 泡 排 序 n);printf(ntt*5-快 速 排 序*6-直接选择排序 n);printf(ntt*7-堆 排 序*8-归 并 排 序 n);printf(ntt*0-退 出*n);printf(ntt*n);-3-printf(ntt 请选择:);scanf(%c,&ch2);getchar();for(i=1;i=L;i+)Ri.key=Si.key;switch(ch2)case 1:printf(ntt 请输入%d 个待排序数据ntt,L);for(i=1;i=L;i+)scanf(%d,&Si.key);getchar

6、();printf(tt);printf(ntt 数据输入完毕！);break;case 2:Insertsort();break;case 3:Shellsort();break;case 4:Bubblesort();break;case 5:printf(ntt 原始数据为（按回车键开始排序）：ntt);for(k=1;k=L;k+)printf(%5d,Rk.key);getchar();printf(n);num=0;sun=0;sum=0;Quicksort(1,L);printf(ntt 排序最终结果是：ntt);for(k=1;k=L;k+)printf(%5d,Rk.key)

7、;printf(ntt 比较次数是：%dntt,sum);-4-printf(ntt 交换次数是：%dntt,sun);break;case 6:Selectsort();break;case 7:Heap();break;case 8:Mergesort();break;case 0:ch1=n;break;default:system(cls);/清屏 printf(ntt 对不起，您输入有误，请重新输入！n);break;if(ch2!=0)if(ch2=2|ch2=3|ch2=4|ch2=5|ch2=6|ch2=7|ch2=8)printf(nntt 排序完毕！);printf(ntt

8、 按回车键继续！);q=getchar();if(q!=n)getchar();ch1=n;return 1;-5-图一 主界面 4.1.1 冒泡排序 核心思想 依次比较相邻的两个数，将小数放在前面，大数放在后面，第一轮比较后，最大的数便被放到了最后；第二轮操作前 n-1 个数据（假设有 n 个数据），依然是依次比较相邻的两个数，将小数放在前面，大数放在后面，倒数第二个数便是第二大的数；同理第 i 轮操作前 n-i+1 的数据（假设 i 取值是从 1 开始的），则n-i+i 位置上的数据为第 i 大的数据。一共有 n-1 轮，第 i 轮比较中共比较 n-i次比较。核心代码 void Bubbl

9、esort()int i,j,k,x=0,y=0,m=0;int exchange=TRUE;/标志位 exchange 初始化为 TRUE 1 printf(ntt 原始数据为（按回车键开始排序）：ntt);for(k=1;k=L;k+)-6-printf(%5d,Rk.key);getchar();printf(n);for(i=1;iL&exchange=TRUE;i+)/外层对总的循环次数执行次数 exchange=FALSE;for(j=1;j=L+1-i;j+)/内层相邻记录的交换与比较 m+;/比较次数+if(Rj.keyRj-1.key)R0.key=Rj.key;Rj.key

10、=Rj-1.key;Rj-1.key=R0.key;exchange=TRUE;y+;/移动次数+m-;/比较次数 if(exchange)/输出语句 printf(tt 第%d 趟冒泡排序的结果为：ntt,i);for(k=1;k=L;k+)printf(%5d,Rk.key);getchar();printf(n);printf(ntt 比较次数是：tt);printf(%d,m);printf(ntt 移动次数是：tt);printf(%d,y);printf(ntt 排序最终结果是：ntt);for(i=1;i=L;i+)printf(%5d,Ri.key);-7-图二 直接插入排序

11、4.1.2 快速排序 核心思想 首先检查数据列表中的数据数，如果小于两个，则直接退出程序。如果有超过两个以上的数据，就选择一个分割点将数据分成两个部分，小于分割点的数据放在一组，其余的放在另一组，然后分别对两组数据排序。通常分割点的数据是随机选取的。这样无论你的数据是否已被排列过，你所分割成的两个字列表的大小是差不多的。而只要两个子列表的大小差不多 核心代码/递归算法实现 void Quicksort(int low,int high)int i=low,j=high,k;R0.key=Rlow.key;while(ij)while(ij&R0.key=Rj.key)/右侧扫描 j-;sum+

12、;-8-if(ij)Ri.key=Rj.key;/交换 i+;sun+;while(ij&Ri.keyR0.key)/左侧扫描 i+;sum+;if(ij)Rj.key=Ri.key;/交换 j-;sun+;Ri.key=R0.key;num+;/输出语句包括排序的结果及次数 printf(tt 第%d 趟快速排序的结果为：ntt,num);for(k=1;k=L;k+)printf(%5d,Rk.key);getchar();printf(n);if(lowi-1)Quicksort(low,i-1);/递归部分(左侧)if(j+1high)Quicksort(j+1,high);/递归部分

13、(右侧)图三 快速排序 -9-4.1.3 直接插入排序 核心思想 经过 i-1 遍处理后,L1.i-1己排好序。第 i 遍处理仅将 Li插入 L1.i-1的适当位置，使得 L1.i又是排好序的序列。要达到这个目的，我们可以用顺序比较的方法。首先比较 Li和 Li-1，如果 Li-1 Li，则 L1.i已排好序，第 i 遍处理就结束了；否则交换 Li与 Li-1的位置，继续比较 Li-1和 Li-2，直到找到某一个位置 j(1ji-1)，使得 Lj Lj+1时为止 核心代码 void Insertsort()int i,j,k,m=0,x=0;/初始化比较次数变量 m，移动次数变量 x prin

14、tf(ntt 原始数据为：（按回车键开始排序）ntt);for(k=1;k=L;k+)printf(%5d,Rk.key);getchar();printf(n);/主要运行部分 for(i=2;i=L;i+)if(Ri.keyRi-1.key)R0=Ri;j=i-1;while(R0.keyRj.key)Rj+1=Rj;j-;Rj+1=R0;x+;m+;/输出语句包括排序的结果及次数 -10-printf(tt 第%d 趟直接插入排序的结果为：ntt,m);for(k=1;k=L;k+)printf(%5d,Rk.key);getchar();printf(n);printf(n);prin

15、tf(ntt 比较次数是：tt);printf(%d,m);printf(ntt 移动次数是：tt);printf(%d,x);printf(ntt 排序最终结果是：ntt);for(i=1;i=L;i+)printf(%5d,Ri.key);图四 直接插入排序 4.1.4 希尔排序 核心思想 先取一个小于 n 的整数 d1 作为第一个增量，把文件的全部记录分成 d1 个组。所有距离为 dl 的倍数的记录放在同一个组中。先在各组内进-11-行直接插入排序；然后，取第二个增量 d2d1 重复上述的分组和排序，直至所取的增量 dt=1(dtdt-ld2d1)，即所有记录放在同一组中进行直接插入排序

16、为止。核心代码 void Shellsort()int i,j,gap,x,k,y=0,m=0;/初始化比较次数变量 m，移动次数变量 y printf(ntt 原始数据为：（按回车键开始排序）ntt);for(k=1;k0)for(i=gap+1;i0)if(Rj.keyRj+gap.key)x=Rj.key;/交换语句 Rj.key=Rj+gap.key;Rj+gap.key=x;j=j-gap;y+;/移动次数+else j=0;gap=gap/2;m+;/比较次数+/输出语句包括排序的结果及次数 printf(tt 第%d 趟希尔排序的结果为：ntt,m);for(k=1;k=L;k+

17、)-12-printf(%5d,Rk.key);getchar();printf(n);printf(ntt 比较次数是：tt);printf(%d,m);printf(ntt 移动次数是：tt);printf(%d,y);printf(ntt 排序最终结果是：ntt);for(i=1;i=L;i+)printf(%5d,Ri.key);printf(n);图五 希尔排序 4.1.5 直接选择排序 核心思想 第一次从 R0Rn-1中选取最小值，与 R0交换，第二次从R1Rn-1中选取最小值，与 R2交换，.，第 i 次从 Ri-1Rn-1中选取最小值，与 Ri-1交换，.，第 n-1 次从 R

18、n-2Rn-1中选取-13-最小值，与 Rn-2交换,总共通过 n-1 次,得到一个按排序码从小到大排列的有序序列.核心代码 void Selectsort()int i,j,k,h,x=0,y=0;printf(ntt 原始数据为（按回车键开始排序）：ntt);for(k=1;k=L;k+)printf(%5d,Rk.key);getchar();printf(n);for(i=1;iL;i+)h=i;for(j=i+1;j=L;j+)x+;/比较次数 if(Rj.keyRh.key)h=j;/确定最小值 if(h!=i)R0.key=Ri.key;Ri.key=Rh.key;Rh.key=

19、R0.key;y+;/移动次数 printf(tt 第%d 趟选择排序的结果为：ntt,i);for(k=1;k=L;k+)printf(%5d,Rk.key);getchar();printf(n);/输出语句包括排序的结果及次数 printf(ntt 比较次数：%d,x);printf(ntt 移动次数：%d,y);printf(ntt 排序最终结果是：ntt);for(i=1;i=L;i+)printf(%5d,Ri.key);printf(n);-14-图六 选择排序 4.1.6 堆排序 核心思想 堆排序是一树形选择排序，在排序过程中，将 R1.N看成是一颗完全二叉树的顺序存储结构，利

20、用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。将原始记录序列建成一个堆，成为初始堆，并输出堆顶元素；调整剩余的记录序列，使之成为一个新堆，再输出堆顶元素；如此反复进行，当堆中只有一个元素时，整个序列的排序结束，输出的序列便是原始序列的非递减有序序列。在堆排序的过程中，主要负责两方面的工作：一是如何将原始记录序列构造成一个堆，即建立初始堆；二是输出堆顶元素后，如何将剩余记录整理成一个新堆。核心代码 void CreateHeap(int root,int index,int*x,int*y)int j,temp,finish;j=2*root;/j 指向左孩子 temp=Rro

21、ot.key;finish=0;while(j=index&finish=0)if(jindex)if(Rj.key=Rj.key)finish=1;else Rj/2.key=Rj.key;(*y)+;j=j*2;*x=*x+2;Rj/2.key=temp;(*y)+;/堆排序 void Heapsort()int i,j,temp,k,x=0,y=0;for(i=(L/2);i=1;i-)/建立初始堆 CreateHeap(i,L,&x,&y);x=0;y=0;for(i=L-1,k=1;i=1;i-,k+)/将堆中根节点和最后一个节点交换 temp=Ri+1.key;Ri+1.key=R

22、1.key;R1.key=temp;CreateHeap(1,i,&x,&y);printf(tt 第%d 趟堆排序的结果为：ntt,k);for(j=1;j=L;j+)printf(%5d,Rj.key);getchar();printf(n);printf(ntt 比较次数是：%dtt,x);-16-printf(ntt 移动次数是：%dtt,y);void Heap()int i;printf(ntt 原始数据为（按回车键开始排序）：ntt);for(i=1;i=L;i+)printf(%5d,Ri.key);getchar();printf(n);Heapsort();printf(n

23、tt 排序最终结果是：ntt);for(i=1;i=L;i+)printf(%5d,Ri.key);printf(n);void Merge(int low,int mm,int high,int*x,int*y)/两个有序序列的合并 int i=low,j=mm+1,p=0;RecType*R1;/i 对第一个开始到结尾，j 从第二个开始到结尾 R1=new RecTypehigh-low+1;if(!R1)printf(内存不足！);while(i=mm&j=high)/两序列从起始位置开始将小的元素放入到 R1中 R1p+=(Ri.key=Rj.key)?Ri+:Rj+;(*x)+;(*

24、y)+;while(i=mm)/第二段结束，剩余放入 R1 中 R1p+=Ri+;(*y)+;while(j=high)/第二段剩余，剩余放入 R1 中 R1p+=Rj+;-17-(*y)+;for(p=0,i=low;i=high;p+,i+)/剩余元素放入 R1 中,赋予 R Ri=R1p;(*y)+;图七 堆排序 4.1.7 归并排序 核心思想 将有 n 个记录的原始序列看作 n 个有序子序列，每个子序列的长度为 1，然后从第一个子序列开始，把相邻的子序列两两合并，得到n/2个长度为2 或 1 的子序列（当子序列个数为奇数时，最后一组合并得到的序列长度为1），把这一过程称为一次归并排序，

25、对第一次归并排序后的n/2个子序列采用上述方法继续顺序成对归并，如此重复，当最后得到的长度为 n 的一个子序列时，该子序列便是原始序列归并排序后的有序序列。核心代码 void MergePass(int length,int*x,int*y)/一次二路归并排序 int i;-18-for(i=1;i+2*length-1=L;i=i+2*length)Merge(i,i+length-1,i+2*length-1,x,y);/函数调用 if(i+length-1L)Merge(i,i+length-1,L,x,y);/函数调用 /归并排序 void Mergesort()/二路归并排序 int

26、 length,k,m=0,i,x=0,y=0;printf(ntt 原始数据为（按回车键开始排序）：ntt);for(k=1;k=L;k+)printf(%5d,Rk.key);getchar();printf(n);for(length=1;lengthL;length*=2)MergePass(length,&x,&y);m+;/输出语句包括排序的结果及次数 printf(tt 第%d 趟归并排序的结果为：ntt,m);for(k=1;k=L;k+)printf(%5d,Rk.key);getchar();printf(n);printf(ntt 排序最终结果是：ntt);for(i=1

27、;i=L;i+)printf(%5d,Ri.key);-19-printf(n);printf(tt 比较次数：%dn,x);printf(tt 移动次数：%dn,y);图八 归并排序 五.总结或心得 回顾这个设计过程,我学到了许多书本上没有学到的知识。通过这次小组制作的程序,丰富了自己的实践技能,扩展了本专业的知识面,使我受益非浅,同时也体验到了搞软件开发的困难度。在这次设计的同时我又从中学到了许多东西。但由于我对这样的排序系统还只是一个开始，了解的不多，这其中或许还有很多的不足,在这里也恳请各位老师能够对我们的作品指明不足并加以改正。总之，在这一次的课程设计过程中，我们查阅了大量的资料，对

28、数据结构有了一点初步的认识，对于网络工程这些辅助性的教材也巩固了不少，为我们这次的课设提供了很大的帮助，锻炼了我们的能力,让我更加熟练了这门程序设计语言：C/C+语言，系统地学习了数据结构方面的知识，并更进一步提高了我们在程序设计、调试方面的技巧。更重要的是，它还让我们认识到了自己的不足，在编程方面，我仅仅是刚刚入门而已，以后的道路任重道远，需要我不断的丰富自己、充实自-20-己，这样才能在程序设计方面有所收获。在最后也感谢我们的小组成员,我在他的帮忙下顺利的做好自己负责的部分.六参考文献 严蔚敏,吴伟明,数据结构(C 语言版),清华大学出版社,2007 年:P263-P288。七附录#inc

29、lude#include#include#define L 8 /排序元素个数#define FALSE 0#define TRUE 1 typedef struct int key;RecType;RecType RL;int num;int sum;int sun;/定义排序趟数的全局变量 /系统主界面 void Bubblesort()int i,j,k,x=0,y=0,m=0;int exchange=TRUE;/标志位 exchange 初始化为 TRUE 1 printf(ntt 原始数据为（按回车键开始排序）：ntt);for(k=1;k=L;k+)printf(%5d,Rk.k

30、ey);getchar();printf(n);for(i=1;iL&exchange=TRUE;i+)/外层对总的循环次数执行次数 exchange=FALSE;for(j=1;j=L+1-i;j+)/内层相邻记录的交换与比较 m+;/比较次数+if(Rj.keyRj-1.key)-21-R0.key=Rj.key;Rj.key=Rj-1.key;Rj-1.key=R0.key;exchange=TRUE;y+;/移动次数+m-;/比较次数 if(exchange)/输出语句 printf(tt 第%d 趟冒泡排序的结果为：ntt,i);for(k=1;k=L;k+)printf(%5d,R

31、k.key);getchar();printf(n);printf(ntt 比较次数是：tt);printf(%d,m);printf(ntt 移动次数是：tt);printf(%d,y);printf(ntt 排序最终结果是：ntt);for(i=1;i=L;i+)printf(%5d,Ri.key);/递归算法实现 void Quicksort(int low,int high)int i=low,j=high,k;R0.key=Rlow.key;while(ij)while(ij&R0.key=Rj.key)/右侧扫描 j-;sum+;if(ij)Ri.key=Rj.key;/交换 i+

32、;sun+;-22-while(ij&Ri.keyR0.key)/左侧扫描 i+;sum+;if(ij)Rj.key=Ri.key;/交换 j-;sun+;Ri.key=R0.key;num+;/输出语句包括排序的结果及次数 printf(tt 第%d 趟快速排序的结果为：ntt,num);for(k=1;k=L;k+)printf(%5d,Rk.key);getchar();printf(n);if(lowi-1)Quicksort(low,i-1);/递归部分(左侧)if(j+1high)Quicksort(j+1,high);/递归部分(右侧)void Insertsort()int i

33、,j,k,m=0,x=0;/初始化比较次数变量 m，移动次数变量 x printf(ntt 原始数据为：（按回车键开始排序）ntt);for(k=1;k=L;k+)printf(%5d,Rk.key);getchar();printf(n);/主要运行部分 for(i=2;i=L;i+)if(Ri.keyRi-1.key)R0=Ri;j=i-1;while(R0.keyRj.key)Rj+1=Rj;-23-j-;Rj+1=R0;x+;m+;/输出语句包括排序的结果及次数 printf(tt 第%d 趟直接插入排序的结果为：ntt,m);for(k=1;k=L;k+)printf(%5d,Rk.

34、key);getchar();printf(n);printf(n);printf(ntt 比较次数是：tt);printf(%d,m);printf(ntt 移动次数是：tt);printf(%d,x);printf(ntt 排序最终结果是：ntt);for(i=1;i=L;i+)printf(%5d,Ri.key);void Shellsort()int i,j,gap,x,k,y=0,m=0;/初始化比较次数变量 m，移动次数变量 y printf(ntt 原始数据为：（按回车键开始排序）ntt);for(k=1;k0)for(i=gap+1;i0)if(Rj.keyRj+gap.key

35、)-24-x=Rj.key;/交换语句 Rj.key=Rj+gap.key;Rj+gap.key=x;j=j-gap;y+;/移动次数+else j=0;gap=gap/2;m+;/比较次数+/输出语句包括排序的结果及次数 printf(tt 第%d 趟希尔排序的结果为：ntt,m);for(k=1;k=L;k+)printf(%5d,Rk.key);getchar();printf(n);printf(ntt 比较次数是：tt);printf(%d,m);printf(ntt 移动次数是：tt);printf(%d,y);printf(ntt 排序最终结果是：ntt);for(i=1;i=L

36、;i+)printf(%5d,Ri.key);printf(n);void Selectsort()int i,j,k,h,x=0,y=0;printf(ntt 原始数据为（按回车键开始排序）：ntt);for(k=1;k=L;k+)printf(%5d,Rk.key);getchar();-25-printf(n);for(i=1;iL;i+)h=i;for(j=i+1;j=L;j+)x+;/比较次数 if(Rj.keyRh.key)h=j;/确定最小值 if(h!=i)R0.key=Ri.key;Ri.key=Rh.key;Rh.key=R0.key;y+;/移动次数 printf(tt

37、第%d 趟选择排序的结果为：ntt,i);for(k=1;k=L;k+)printf(%5d,Rk.key);getchar();printf(n);/输出语句包括排序的结果及次数 printf(ntt 比较次数：%d,x);printf(ntt 移动次数：%d,y);printf(ntt 排序最终结果是：ntt);for(i=1;i=L;i+)printf(%5d,Ri.key);printf(n);void CreateHeap(int root,int index,int*x,int*y)int j,temp,finish;j=2*root;/j 指向左孩子 temp=Rroot.key

38、;finish=0;while(j=index&finish=0)-26-if(jindex)if(Rj.key=Rj.key)finish=1;else Rj/2.key=Rj.key;(*y)+;j=j*2;*x=*x+2;Rj/2.key=temp;(*y)+;/堆排序 void Heapsort()int i,j,temp,k,x=0,y=0;for(i=(L/2);i=1;i-)/建立初始堆 CreateHeap(i,L,&x,&y);x=0;y=0;for(i=L-1,k=1;i=1;i-,k+)/将堆中根节点和最后一个节点交换 temp=Ri+1.key;Ri+1.key=R1.

39、key;R1.key=temp;CreateHeap(1,i,&x,&y);printf(tt 第%d 趟堆排序的结果为：ntt,k);for(j=1;j=L;j+)printf(%5d,Rj.key);getchar();-27-printf(n);printf(ntt 比较次数是：%dtt,x);printf(ntt 移动次数是：%dtt,y);void Heap()int i;printf(ntt 原始数据为（按回车键开始排序）：ntt);for(i=1;i=L;i+)printf(%5d,Ri.key);getchar();printf(n);Heapsort();printf(ntt

40、 排序最终结果是：ntt);for(i=1;i=L;i+)printf(%5d,Ri.key);printf(n);void Merge(int low,int mm,int high,int*x,int*y)/两个有序序列的合并 int i=low,j=mm+1,p=0;RecType*R1;/i 对第一个开始到结尾，j 从第二个开始到结尾 R1=new RecTypehigh-low+1;if(!R1)printf(内存不足！);while(i=mm&j=high)/两序列从起始位置开始将小的元素放入到 R1 中 R1p+=(Ri.key=Rj.key)?Ri+:Rj+;(*x)+;(*y

41、)+;while(i=mm)/第二段结束，剩余放入 R1 中 R1p+=Ri+;(*y)+;while(j=high)/第二段剩余，剩余放入 R1 中 -28-R1p+=Rj+;(*y)+;for(p=0,i=low;i=high;p+,i+)/剩余元素放入 R1 中,赋予 R Ri=R1p;(*y)+;void MergePass(int length,int*x,int*y)/一次二路归并排序 int i;for(i=1;i+2*length-1=L;i=i+2*length)Merge(i,i+length-1,i+2*length-1,x,y);/函数调用 if(i+length-1L

42、)Merge(i,i+length-1,L,x,y);/函数调用 /归并排序 void Mergesort()/二路归并排序 int length,k,m=0,i,x=0,y=0;printf(ntt 原始数据为（按回车键开始排序）：ntt);for(k=1;k=L;k+)printf(%5d,Rk.key);getchar();printf(n);for(length=1;lengthL;length*=2)MergePass(length,&x,&y);m+;/输出语句包括排序的结果及次数 printf(tt 第%d 趟归并排序的结果为：ntt,m);for(k=1;k=L;k+)prin

43、tf(%5d,Rk.key);getchar();printf(n);printf(ntt 排序最终结果是：ntt);for(i=1;i=L;i+)printf(%5d,Ri.key);printf(n);printf(tt 比较次数：%dn,x);-29-printf(tt 移动次数：%dn,y);/主函数 int main()RecType S100;int i,k;char ch1,ch2,q;printf(ntt*排序算法演示系统*nntt 请输入%d 个待排序的数据：n,L);for(i=1;i=L;i+)printf(tt 请输入第%dth 数据:,i);scanf(%d,&Si.

44、key);getchar();ch1=y;while(ch1=y)printf(ntt 菜 单 n);printf(ntt*n);printf(ntt*1-更新排序数据 *2-直接插入排序 n);printf(ntt*3-希 尔 排 序 *4-冒 泡 排 序 n);printf(ntt*5-快 速 排 序 *6-直接选择排序 n);printf(ntt*7-堆 排 序 *8-归 并 排 序 n);printf(ntt*0-退 出*n);printf(ntt*n);printf(ntt 请选择:);scanf(%c,&ch2);getchar();for(i=1;i=L;i+)Ri.key=Si

45、.key;switch(ch2)case 1:printf(ntt 请输入%d 个待排序数据ntt,L);for(i=1;i=L;i+)scanf(%d,&Si.key);getchar();printf(tt);-30-printf(ntt 数据输入完毕！);break;case 2:Insertsort();break;case 3:Shellsort();break;case 4:Bubblesort();break;case 5:printf(ntt 原始数据为（按回车键开始排序）：ntt);for(k=1;k=L;k+)printf(%5d,Rk.key);getchar();pri

46、ntf(n);num=0;sun=0;sum=0;Quicksort(1,L);printf(ntt 排序最终结果是：ntt);for(k=1;k=L;k+)printf(%5d,Rk.key);printf(ntt 比较次数是：%dntt,sum);printf(ntt 交换次数是：%dntt,sun);break;case 6:Selectsort();break;case 7:Heap();break;case 8:Mergesort();break;case 0:ch1=n;break;default:system(cls);/清屏 -31-printf(ntt 对不起，您输入有误，请重新输入！n);break;if(ch2!=0)if(ch2=2|ch2=3|ch2=4|ch2=5|ch2=6|ch2=7|ch2=8)printf(nntt 排序完毕！);printf(ntt 按回车键继续！);q=getchar();if(q!=n)getchar();ch1=n;return 1;