西北工业大学-程序设计大作业(共19页).doc

《西北工业大学-程序设计大作业(共19页).doc》由会员分享，可在线阅读，更多相关《西北工业大学-程序设计大作业(共19页).doc（19页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上学 院学院班 级学 号姓 名目录1 摘要1.1 设计题目算法型大作业题目：编写七种排序算法的演示程序。1.2 设计内容编写快速排序、插入排序、选择排序、冒泡排序、堆排序、归并排序、基数排序函数，通过主函数调用以实现七种排序算法的演示。1.3 开发工具Visual C+ 6.01.4 应用平台Windows 2000/XP/Vista 32位2 详细设计2.1 程序结构程序的整体结构与流程见下图所示。程序运行时在主菜单中输入序号选择排序方法或选择结束程序，当进行某种排序方法后，在主函数中输入待排数据个数和待排数据，通过调用对应的排序函数实现排序并输出。该排序结束后再次进

2、入主函数，通过循环重复上述操作。其中，主函数中将数组地址和待排序数据个数传递给排序函数，在排序函数中实现排序功能。输出排序结果开始快速插入选择冒泡堆排归并基数选择排序方法进入主菜单退出系统2.2 主要功能函数的功能为对快速排序、插入排序、选择排序、冒泡排序、堆排序、归并排序、基数排序算法的演示。主函数：程序运行时，可使运行者根据提醒输入相关操作，从而进入不同的排序方法或者退出。快速排序函数：根据快速排序的算法，最后输出插入排序函数：根据插入排序的算法，最后输出选择排序函数：根据选择排序的算法，最后输出冒泡排序函数：根据冒泡排序的算法，最后输出堆排序函数：根据堆排序的算法，最后输出归并排序函数：

3、根据归并排序的算法，最后输出基数排序函数：根据基数排序的算法，最后输出2.3 函数实现主函数:在主函数中对菜单输出，通过switch语句中的case分支选择所需要的排序方法；通过while循环使演示程序在运行时能够持续进行快速排序： 快速排序（kuaisu）又被称做分区交换排序，这是一种平均性能非常好的排序方法。其算法基本思想是：任取排序表中的某个数据元素(例如取第一个数据元素)作为基准，按照该数据元素的关键字大小，将整个排序表划分为左右两个子表： 左侧子表中所有数据元素的关键字都小于基准数据元素的关键字。右侧子表中所有数据元素的关键字都大于或等于基准数据元素的关键字，基准数据元素则排在这两个

4、子表中间(这也是该数据元素最终应安放的位置)，然后分别对这两个子表重复施行上述方法的快速排序，直到所有的子表长度为1，则排序结束。插入排序：插入排序（charu）的基本思想：开始时把第一个数据元素作为初始的有序序列，然后从第二个数据元素开始依次把数据元素按关键字大小插入到已排序的部分排序表的适当位置。当插入第i(1i=n)个数据元素时，前面的i-1个数据元素已经排好序，这时，用第i个数据元素的关键字与前面的i-1个数据元素的关键字顺序进行比较，找到插入位置后就将第i个数据元素插入。如此进行n-1次插入，就完成了排序。以下是在顺序表上实现的直接插入排序在顺序表上进行直接插入排序时，当插入第i(1

5、i=n)个数据元素时，前面的A0、A1、Ai-2已经排好序，这时，用Ai-1的关键字依次与Ai-2,Ai-3,的关键字顺序进行比较，如果这些数据元素的关键字大于Ai-1的关键字，则将数据元素向后移一个位置，当找到插入位置后就将Ai-1插入，就完成了A0,A1,An-1的排序。选择排序选择排序（xuanze）的算法基本思想是：a)开始时设i的初始值为0。b)如果i=n，因此在则趟归并中while循环不执行，只做把temptable.arr中的数据元素复制到table.arr的工作。基数排序：“基数排序法”（radix sort）则是属于“分配式排序”（distribution sort），基数排

6、序法又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的比较性排序法。具体可以参看后面的代码进行理解。其它：使用了stdlib头文件里包含的系统函数，包括清屏函数和运行时的暂停，增强了程序运行时的效果。2.4 开发日志在老师布置了大作业的题目后，我就把题目下载下来并进行分析已选择合适的题目。经过我的慎重考虑，选择了算法型大作业题目中的编写七种排序算法的演示程序

7、，觉得自己有能力把这道题目很好完成。在认真分析连题目后，基本确定了整体的思路，但是其中有堆排序，归并排序，基数排序我没有在教材中接触过，于是借助了图书馆和网络上的资源，重点对这三的函数进行编写。在编写大作业过程中大的困难我没有遇到，只是有些小的疏忽常常导致程序无法运行，如形参和实参的不一致等。我也在其中意识到对知识掌握的不够熟练，在解决了这些问题后，我觉得自己对程序的编写更加熟练了，对问题的分析也更加严谨了。在C程序设计的实验和理论考试之前代码已基本完成。在考试结束后，我又对程序稍微进行了修改，使之运行时效果更好。接着开始写实验报告，整理自己的大作业。我对我的作业是很满意的。3 程序调试及运行

8、3.1 程序运行结果1.进入程序运行后所显示的菜单：2.快速排序：3.插入排序：4.选择排序：5.冒泡排序：6.堆排序：7.归并排序：8.基数排序：9.结束：3.2 程序使用说明1.打开源程序，调试完毕后开始运行，开始进行七种算法的演示；2.按照说明进行输入,选择数字17即可进入相应的排序算法演示程序，选择8结束程序；3.选择排序的方法后，按要求输入待排数据的个数，然后输入待排序数据即可（数据排序结束后，会自动清屏，进入菜单进行接下来的选择）；4.应当注意，本演示程序对数据进行的是升序；3.3 程序开发总结在选择这个题目时，我觉得难度系数10对我有挑战性，并且我对排序有相对比较熟悉，所以就选了

9、这个题目。但是在编写过程中却遇到很多问题。我和我的同学进行了讨论，查阅了图书馆和网络上的资料，结合力我个人对本题目的理解对各种问题进行了处理，学到了很多教材上没有的知识。从这次实践中，我意识到自己还有很多不足之处。能力也得到了提高。我在进行编程时还需要翻书查找，对于这一点，只能说对知识的学习还不够扎实，所以有空时还应该继续熟悉这门课程。另外，就是对于错误的处理，不能得心应手，不能正确处理一些简单的错误。对于逻辑上的错误，不能够立即找到出错点，往往需要向同学请教才能找出错误，并且改正。我觉得这是自己独自思考能力不高的问题，遇事需要自己仔细想想，若还不能改正，再请教别人也不迟。从总体上说，最终结果

10、我很满意，我觉得我所设计的程序操作方便，功能良好。我在上面花费了很多时间和精力，对作业不断进行修改和完善，我很有成就感 。我的能力在这之中得到了提高。4 附件（源程序）# include# include/*快速排序*/void kuaisu(int A,int n)int i,j,k,t,p;for(i=0;in-1;i+)k=i;for(j=i+1;jn;j+)if(AjAk) k=j;t=Ak;Ak=Ai;Ai=t;printf(第%d趟:,i+1);for(p=0;pn;p+)printf(%d ,Ap);printf(n);printf(n排序结果:);for(i=0;in;i+)p

11、rintf(%d ,Ai);printf(n);printf(n);system(pause);system(CLS);/*插入排序*/void charu(int A,int n) int i,k,t,j,h=1;for(i=1;in;i+)t=Ai;k=i-1;while(tAk)Ak+1=Ak;k-;if(k=-1)break;printf(第%d趟:,h+);for(j=0;jn;j+)printf(%d ,Aj);printf(n);Ak+1=t;printf(n排序结果:);for(i=0;in;i+)printf(%d ,Ai);printf(n);printf(n);syste

12、m(pause);system(CLS);/*选择排序*/void xuanze(int A,int n) int i,j,k,t,l,h=1;for(i=0;in-1;i+)k=i;for(j=i+1;jn;j+)if(AjAk) k=j;if(i!=k)t=Ai;Ai=Ak;Ak=t;printf(第%d趟:,h+);for(l=0;ln;l+)printf(%d ,Al);printf(n);printf(n排序结果:);for(i=0;in;i+)printf(%d ,Ai);printf(n);printf(n);system(pause);system(CLS);/*冒泡排序*/v

13、oid maopao(int A,int n) int i,j,t,h=1,p;for(j=0;jn-1;j+)for(i=0;iAi+1)t=Ai,Ai=Ai+1,Ai+1=t,p+;printf(第%d趟:,h+);for(p=0;pn;p+)printf(%d ,Ap);printf(n);printf(n排序结果:);for(i=0;in;i+)printf(%d ,Ai);printf(n);printf(n);system(pause);system(CLS);/*堆排序*/void shift(int A , int i , int m) int k,t; t=Ai;k=2*i+

14、1; while (km) if(km-1)&(AkAk+1) k+; if(t=0;i-)shift(A,i,n); for (i=n-1;i=1;i-)k=A0;A0=Ai;Ai=k;shift(A,0,i);printf(第%d趟:,h+);for(j=0;jn;j+)printf(%d ,Aj);printf(n);printf(n排序结果:);for(i=0;in;i+)printf(%d ,Ai);printf(n);printf(n);system(pause);system(CLS);/*归并排序*/void merge(int number,int first,int las

15、t,int mid) int number_temp10=0; int i=first,j=mid+1,k; for(k=0;k=last-first;k+) if (i=mid+1) number_tempk=numberj+; continue; if (j=last+1) number_tempk=numberi+; continue; if (numberinumberj) number_tempk=numberi+; else number_tempk=numberj+; for (i=first,j=0;i=last;i+,j+) numberi = number_tempj;vo

16、id merge_sort(int number,int first,int last) int mid=0; if(firstlast) mid=(first+last)/2; merge_sort(number,first,mid); merge_sort(number,mid+1,last); merge(number,first,last,mid); void guibing(int a,int n)int i;merge_sort(a,0,n-1);printf(n排序结果:);for(i=0;in;i+) printf(%d ,ai);printf(n);printf(n);sys

17、tem(pause);system(CLS);/*基数排序*/void jishu(int data,int n)int temp1010=0; int order10=0; int i,j,k,q,lsd; k=0; q=1; while(q=n) for(i=0;in;i+) lsd=(datai/q)%n); templsdorderlsd=datai; orderlsd+; for(i=0;in;i+) if(orderi != 0) for(j=0;jorderi;j+) datak=tempij; k+; orderi = 0; q *= n; k = 0; printf(n排序结

18、果:);for(i=0;in;i+)printf(%d ,datai);printf(n);printf(n);system(pause);system(CLS); /*主函数*/ int main()int A100,p,n,i;while(1)printf(nt* 七种排序算法的演示程序 *n);printf(t* *n);printf(t* 1-快速排序 *n);printf(t* 2-插入排序 *n);printf(t* 3-选择排序 *n);printf(t* 4-冒泡排序 *n);printf(t* 5- 堆排序 *n);printf(t* 6-归并排序 *n);printf(t*

19、 7-基数排序 *n);printf(t* 8-退出程序 *n);printf(t* *n);printf(t*nn);printf(请输入序号进行选择:n);scanf(%d,&p);if(p=8)break;printf(请输入待排序数的个数:n);scanf(%d,&n);printf(请输入待排序数据:n);for(i=0;in;i+)scanf(%d,&Ai);switch(p)case 1:kuaisu(A,n);break;case 2:charu(A,n);break;case 3:xuanze(A,n);break;case 4:maopao(A,n);break;case 5:duipai(A,n);break;case 6:guibing(A,n);break;case 7:jishu(A,n);break;printf(nntttt谢谢您的使用nn);return 0;专心-专注-专业