c语言排序大作业

1、作业名称：七种排序的算法演示学院：Xxx班级：Xxx学号：Xxx姓名：Zwc团队组成：Zwc请填写以下十项内容，将表格按页对齐（插入空行），勿删除任何部分。1、问题与背景（描述程序所要解决的问题或应用背景）我们学习了多种排序方法，但不清楚这么多种排序方法分别适合在什么情况下使用，该演示程序将体现各排序方式之间的区别，以帮助我们更深层次的了解这些排序。对冒泡排序、选择排序、插入排序、快速排序、堆排序、归弁排序、基数排序进行演示，观察这七种排序的速度和排序过程。其中归弁排序、基数排序无法查看排序的“每一趟”，只能看到排序结果，可通过查看源代码进行分析其排序的原理。其他排序可通过查看每一趟的排序结果

2、分析其排序的原理和过程，弁比较各种排序方法的优点和缺点。2、开发工具（列出所使用的开发工具和第3方开发库）Code:block3、主要功能（详细说明程序的功能）对七种排序进行演示，选择所需要的排序输入所需输入的数字数和所需排序的数字，输出每一趟的排序结果（没有每一趟排序结果的直接输出排序结果）。通过对输出每一趟的排序结果或运行时间来分析各种排序的运行方式和排序速度。其优点在于通过主函数调用多种排序方式，且不必关闭程序可多次选择运行的方式或者选择关闭程序。4、设计内容（详细描述解决问题的原理和方法、算法、数据结构等）结构图如图所示:通过在主函数中调用显示函数和各排序函数实现各个排序演示或结束程序

3、。输入排序数字的数量和需排序数字，输出排序结果或者选择退出程序。5、程序文件与工程名称(标出程序中所有文件名、工程名称及其说明)源文件:排序.c头文件:paixu.hdisolay.c应用程序：排序.exeO文件：排序.o6、函数模块(程序中各个函数的原型声明及其说明)主函数：在主函数中对菜单输出，通过switch语句中的case分支选择所需要的排序方法；通过while循环使演示程序在运行时能够持续进行快速排序(quicksort)又被称做分区交换排序，这是一种平均性能非常好的排序方法。插入排序(insertionsort)的基本思想：开始时把第一个数据元素作为初始的有序序列，然后从第二个数据

4、元素开始依次把数据元素按关键字大小插入到已排序的部分排序表的适当位置。选择排序：选择排序(selectsort)a)开始时设i的初始值为0。b)如果i<n-1,在数据元素序列Ai(An-1中，选出具有最小关键字的数据元素Ak；否则算法结束。c）若Ak不是这组数据元素中的第一个数据元素（i*k）,则将Ak与Ai这两数据元素的位置对调；d）令i=i+1转步骤b）。冒泡排序（bubblesort）的基本思想是：设排序表中有n个数据元素。首先对排序表中第一，二个数据元素的关键字A0和A1进行比较。如果前者大于后者，则进行交换；然后对第二，三个数据做同样的处理；重复此过程直到处理完最后两个相邻的数

5、据元素。堆排序（heapsort）:a.对排序表中的数据元素，利用堆的调整算法形成初始堆。b.输出堆顶元素。c.对剩余元素重新调整形成堆。d.重复执行第b、c步，直到所有数据元素被输出。如果建立的堆满足最大堆的条件，则堆的第一个数据元素A0具有最大的关键字，将A0与An-1对调，把具有最大关键字的数据元素交换到最后，再对前面的n-1个数据元素使用堆的调整算法，重新建立最大堆，结果把具有次最大关键字的数据元素又上浮到堆顶，即A0的位置，再对调A0和An-2,如此反复执行n-1次，最后得到全部排序好的数据元素序列。归弁排序（mergesort）基本思想是：设有两个有序表A和B,其数据元素个数（表长

6、）分别为n和m,变量i和j分别是表A和表B的当前检测指针；设表C是归弁后的新有序表，变量k是它的当前存放指针。开始时i、j、k都分别指向A、B、C三个表的起始位置；然后根据Ai与Bj的关键字的大小，把关键字小的数据元素放到新表Ck中；且相应的检测指针（i或j）和存放指针k增加1.如此循环，当i与j中有一个已经超出表长时，将另一个表中的剩余部分照抄到新表CkCm+n中。下面的归弁算法中，两个待归弁的有序表首尾相接存放在数组sourcetable.arr中，其中第一个表的下标范围从left至|mid,另一个表的下标范围从mid+1到right。前一个表中有mid-left+1个数据元素，后一个表中

7、有right-mid个数据元素。归弁后得到的新有序表有right-mid个数据元素。归弁后得到的新有序表存放在另一个辅助数组mergedtable.arr中,其下标范围从left到right。一趟归弁算法：设数组sourcetable.arr0到sourcetable.arrn-1中的n个数据元素已经分为一些长度为len的归弁项，将这些归弁项两两归弁，归弁成一些长度为2len的归弁项，结果放到mergedtable.arr中。如果n不是2len的整数倍，则一趟归弁到最后，可能遇到两种情况：剩下一个长度为len的归弁项和一个长度不足len的归弁项，可用一次merge算法，将它们归弁成一个长度小于

8、2len的归弁项。只剩下一个归弁项，其长度小于或等于len,可将它直接复制到数组mergedtable.arr中。在一趟归弁算法的基础上，实现两路归弁排序算法。在两路归弁排序算法中，初始排序表存放在数组table.arr中，第一趟归弁将table.arr中的归弁项两两归弁，结果存放在辅助数组temptable.arr中。第二趟将temptable.arr中的归弁项两两归弁，结果放回原数组table.arr中，如此反复进行。为了将最后归弁结果仍放在数组table.arr中，归弁趟数应为偶数。如果做奇数趟就能完成时，最后还需要执行一次一趟归弁过程，由于这时的归弁项长度len>=n,因此在则趟

9、归弁中while循环不执行，只做把temptable.arr中的数据元素复制到table.arr的工作。基数排序：“基数排序法”(radixsort)则是属于“分配式排序”(distributionsort),基数排序法又称“桶子法”(bucketsort)或binsort,顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O(nlog(r)m),其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的比较性排序法。具体可以参看后面的代码进行理解。7、使用说明(运行程序的小型说明书)看到主菜单后根

10、据主菜单选择所需要的排序方式，然后根据提示输入所需排序的数字数和需排序的数字。若有每一趟的排序结果，没按一次回车键可显示一趟的结果，否则直接输出排序结果。输出结果后再按一次回车键，再次显示主菜单，可根据需要再次选择排序方式或选择退出，若选择退出程序(over),还需输入完数字数和数字后才能你退出，因此建议若需要退出程序，选择退出选项后再次输入所需排序数为0,方可退出程序。8、程序开发总结（简要叙述编写本作业的收获与思考）第一次做大作业，发现了自己很多不足，在程序的优化和逻辑方面还需要继续研究和完善。同坐这次的程序开发，使我对各排序有了更深入的了解，虽然程序中归弁排序和基数排序对于我来说还是很难

11、理解，但为了完善这个程序，决定先运用该排序今后再继续深入研究。完成该程序设计后，感到深深的满足感，这是第一次写头文件以及第一次写这么长的代码，既是对自己的一次检阅，也是对自己的一次自我提升。9、运行截图（附上程序运行的截图画面，至少有1幅，截图越翔实得分越高）Windows中抓取当前活动窗口：Alt+PrintScreen,抓取全屏：PrintScreeno或者使用HyperSnap等软件（百度搜索）。1、 主菜单*亡小f488凯口仁出。口工试用文怦0可序大作业出日序，“-X*不*手*聿*李*手cP1aueqh123456782、冒泡排序C:LI犍rs8BBBe5ktopV椭文件5句的序大作业

12、WE序.-X*奉*卡*奉*率*.*浓*1bubblesort*2selectsort*3insertionsort*4quicksort*5heapsort*6mergesort*1radixsort*Sover*输入要选择的排序：1倒入要输入的数字数：输入需要排序的数字：32651第1趟:365213、薪趟:65321选择排序1C:UsenB8明Dcsktop试用文彳中1noj蜜E序大作业谊E序.-Xii|e|e比*91bubblesort*2selectsort*3insertionsort*4quicksort*+5heapsort*&mergesort*7radixsort+*

13、8over*我做aa之.*字申*：*：*二*常青前人要选择的排序；"",人要输入的数字数：髭入需要排序的数字：12651婚I越：62351第2题;53214、插入排序匚'Users卷&总试用文件UiQjaF序大作业&非序启出”-X* 1bubblesort+* 2selectsori* 3insertionsort+* 4quicksort*率5heapsort* 6mergesort* 7radixsort”* 6over* *+*我*五*五*五*五*五引人要选择的排序：输入要输入的数字数:5输入需要排序的数字:第.趟:32651第2趟:63251

14、第3趟:653215、快速排序"CAU&eM8gatDEsktcip"试用文件noj排序大作业排序段-X*率*率*率*聿*率*:*:*bubblesort*+selectsort*insertionsort*quicksort*heapsort+*mergesort*7radixsort*+8ver*输入要选篇赢落广邮邮除*输入要输入的数字数：6输入需要排序的数字：3265165321率*39c*东李东李申*率*字*率*4c*1bubblesort*2selectsort*3insertionsort*4quicksort*5heapsort*6mergesort*

15、7radixsort*8over*输入要选/霸霹:L*6、堆排序C:Users888Desktop试用文件no_j由F序大作业管F序Hxe>b-JL-:T-A-.gij,-U3*-2-g-_：«4_.，U='"'_：4-L-.Uh"J一上.y12345678bubblesortselectsortinsertionsortquicksortheapsortmergesortradixsortover3265第1趟2第2趟3第3趟5第4趟6663352227、归弁排序i1:r；,单;,单;rw；ra：r7r7r!<pB；r；r.萌irT&

16、quot;"1=；，r；=f，；，单;r费jr号ra；r:r；r年,»iT?bubblesort*selectsort*insertionsort*quicksort*heapsort*mergesort*radixsort*over*Pp"Pg?"Pj?r1Pjn?Ji?J?PsP|C'?!?!5SpS输入要选择的排序：俞人要输入的数字数:露入需要排序的数字;2651东无法显示排序过程*排序结果:123568、基数排序*1bubblesort*2selectsort*3insertionsort*quicksort*heapsort*merge

17、sort第*radixsort*8over*输入要选择的排序：输入要输入的数字数：谛入需要排序的数字i32651*无法显示排序过程*排序结果；12356* *率肱*率*率*肱*率* 1bubblesort"* 2selectsort* 3insertionsort* 4quicksort* 5heapsort* 6mergesort* 7radixsort生* 8over* *率*率*输入要选择的排序：9、结束，退出程序CAUseE8S8De或匕p试用文件皿句冒序大作业期非触入要输入的数字数：露人需要排序的数字，32651*无法显示排序过程*排序结果：12356*1bubblesor

18、t*2selectsort*3insertionsort*4quicksort*5heapsort*6mergesort*7radixsort*8over*h«输入要选择的排序；8输入要输入的数字数;0输入需要排序的数字：结束Processreturned0(0x0)executiontime:140.896sPressanykeytocontinue.10、源程序(附上程序源代码，若是多个文件，标出文件名)排序.C#include<stdio.h>#include"paixu.h"#include"display.h"intmai

19、n()(intA100000,n,x,y,left,right;charc,ch;L:xianshi();printf("输入要选择的排序：n");scanf("%d",&y);left=0;right=n-1;printf("输入要输入的数字数：n");scanf("%d",&n);printf("输入需要排序的数字：n");for(x=0;x<n;x+)scanf("%d”,&Ax);switch(y)(case1:bubblesort(A,n);ch

20、=getchar();break;case2:selectsort(A,n);ch=getchar();break;case3:insertionsort(A,n);ch=getchar();break;case4:quicksort(A,n,left,right);ch=getchar();break;case5:heapsort(A,n);ch=getchar();break;case6:mergesort(A,n);ch=getchar();break;case7:radixsort(A,n);ch=getchar();break;case8:printf("结束")

21、;return0;gotoL;paixu.h#include<stdio.h>voidheapadjust(intA,inti,intlength);voidmerges(intnumber口,intfirst,intlast,intmid);voidmerge_sort(intnumber口,intfirst,intlast);voidbubblesort(intA,intn)/冒泡排序inti,j,t,k,m=0;charch;for(i=0;i<n-1;i+)for(j=0;j<n-1-i;j+)if(Aj<Aj+1)(t=Aj;Aj=Aj+1;Aj+1=t

22、;)ch=getchar();printf("第遍:",i+1);for(k=0;k<n;k+)printf("%d",Ak);m=0;for(k=0;k<n-1;k+)if(Ak>Ak+1)m+;if(m=n-1)break;)printf("n");)voidselectsort(intA,intn)/选择排序(inti,j,t,k,m=0;charch;for(i=0;i<n-1;i+)(k=i;for(j=i+1;j<n;j+)if(Aj>Ak)k=j;if(i!=k)(t=Ai;Ai=Ak

23、;Ak=t;)ch=getchar();printff'第遍二i+1);for(k=0;k<n;k+)printf("%d",Ak);m=0;for(k=0;k<n-1;k+)if(Ak>Ak+1)m+;if(m=n-1)break;)printf("n");插入排序voidinsertionsort(intA,intn)/(inti,j,t,k,m=0;charch;for(i=1;i<n;i+)(t=Ai;k=i-1;while(t>Ak)(Ak+1=Ak;k-;if(k=-1)break;Ak+1=t;ch=g

24、etchar();printf("第逾:",i);for(k=0;k<n;k+)printf("%d",Ak);m=0;for(k=0;k<n-1;k+)if(Ak>Ak+1)m+;if(m=n-1)break;printf("n");)voidquicksort(intA,intn,intleft,intright)/快速排序inti,j,t,k,m=0;charch;if(left<right)i=left;j=right+1;while(1)while(i+1<n&&A+i>A

25、left);while(j-i>-1&&A-j<Aleft);if(i>=j)break;t=Ai;Ai=Aj;Aj=t;)t=Aleft,Aleft=Aj,Aj=t;ch=getchar();for(k=0;k<n;k+)printf("%d",Ak);m=0;for(k=0;k<right-left;k+)if(Ak>Ak+1)m+;if(m=right-left)return;/若已为降序则退出quicksort(A,n,left,j-1);quicksort(A,n,j+1,right);printf("

26、n");voidheapsort(intA,intlength)/堆排序inti,j,t,k,m=0;charch;for(i=length/2-1;i>=0;-i)heapadjust(A,i,length);for(i=length-1;i>0;-i)Ai=A0AAi;/实际为二者交换值A0=A0AAi;Ai=A0AAi;heapadjust(A,0,i);ch=getchar();printf("第调",length-i);for(k=0;k<length;k+)printf("%d",Ak);m=0;for(k=0;k

27、<length-1;k+)if(Ak>Ak+1)m+;if(m=length-1)break;printf("n");voidmergesort(intA,intn)/归并排序inti;merge_sort(A,0,n-1);printf("*无法显示排序过程*n排序结果:");for(i=0;i<n;i+)printf("%d",Ai);printf("n");voidradixsort(intA,intn)inttemp1010=0;intorder10=0;inti,j,k,q,lsd;k=

28、0;q=1;while(q<=n)(for(i=0;i<n;i+)(lsd=(Ai/q)%n);templsdorderlsd=Ai;orderlsd+;for(i=0;i<n;i+)(if(orderi!=0)for(j=0;j<orderi;j+)(Ak=tempij;k+;orderi=0;q*=n;k=0;printf("*无法显示排序过程*n排序结果:");for(i=0;i<n;i+)printf("%d",Ai);printf("n");)voidheapadjust(intA,inti,intlength)/堆调整(intchild,temp;for(;2*i+1<length;i=child)(child=2*i+1;if(child<length-1&&am