内部排序算法比较课程设计报告7种基本排序

1、合肥学院计算机科学与技术系课程设计报告20172018学年第一学期课程数据结构与算法课程设计名称内部排序算法比较学生姓名邀岂学号1504012027专业班级计算机科学与技术系15级2班指导教师2017年9月1、问题分析和任务定义各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间，存在一定的却缺陷。我们将通过随机的数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。所设计的程序应能够将产生的随机数据同时用不同的内部排序算法排序，并列出关键字比较次数与移动次数，方便比较。待排序表的表长不少于100,为方便起见，我们令表长等于100,用5组随机的数据排序的结果作

2、比较。2、数据结构的选择和概要设计一.可能排序表的抽象数据类型定义：ADTOrderableList数据对象：D=a、|+eIntegerSet,i=1,2,n,n>0数据关系：R1=<LlJn|&LlleCD,i=2,n基本操作：InitList(n)操作结果：构造一个长度为n,元素值依次为1,2,n的有序表。RandomizeList(d,isInverseOrder)操作结果：首先根据isInverseOrder为True或False,将表置为逆序或正序，然后将表进行d(0wdw8)级随机打乱。d为0时表不打乱，d越大，打乱程度越高。RecallList()操作结果：

3、恢复最后一次用RandomizeList随机大乱的可排序表。ListLength()操作结果：返回可排序的长度。ListEmpty()操作结果：若可排序表为空表，则返回True,否则返回False。BubbleSort(&c,&s)C和移动次数SoC和移动次数SoC和移动次数SoC和移动次数SoC和移动次数SoC和移动次数So操作结果：进行冒泡排序，返回关键字比较次数InsertSort(&c,&s)操作结果：进行插入排序，返回关键字比较次数SelectSort(&c,&s)操作结果：进行选择排序，返回关键字比较次数QuickSort(&

4、c,&s)操作结果：进行快速排序，返回关键字比较次数ShellSort(&c,&s)操作结果：进行希尔排序，返回关键字比较次数HeapSort(&c,&s)操作结果：进行堆排序，返回关键字比较次数ListTraveres(visit。)操作结果：依次对L中的每个元素调用函数visit()。ADTOrderableList二.概要设计：1 .冒泡排序：冒泡排序的基本概念是：依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数,将小数放前，大数放后，如此继续，直至比较最后两

5、个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。如此下去，重复以上过程，直至最终完成排序。2 .直接插入排序：直接插入排序是一种最简单的排序方法，它的基本操作是将一个记录插入到已牌号序的有序表中，从而得到一个新的、记录数增1的有序表。3 .简单选择排序：在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩

6、下的数当中再找最小的与第二个位置的数交换，如此循环。4 .希尔排序：希尔排序又称“缩小增量排序”，它也是一种属插入排序类的方法，但在时间效率上较前述集中排序方法有较大的改进。它的基本思想是：先将整个待排序记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。5 .堆排序：由二叉堆的定义可知，堆顶元素（即二叉堆的根节点）一定为堆中的最大值或最小值，因此如果我们输出堆顶元素后，将剩余的元素再调整为二叉堆，继而再次输出堆顶元素，再将剩余的元素调整为二叉堆，反复执行该过程，这样便可输出一个有序序列，这个过程我们就叫做堆排序。6 .归并排序：

7、归并的含义很明显就是将两个或者两个以上的有序表组合成一个新的有序表。归并排序中一般所用到的是2-路归并排序，即将含有n个元素的序列看成是n个有序的子序列，每个子序列的长度为1,而后两两合并，得到n/2个长度为2或1的有序子序列，再进行两两合并。直到最后由两个有序的子序列合并成为一个长度为n的有序序列。2-路归并的核心操作是将一维数组中前后相邻的两个有序序列归并为一个有序序列。7 .快速排序：快速排序的基本实现思想就是将当前待排序列分成两个部分、一个值。一个值：就是选定出一个值作为被比较的元素。两个部分：所有比该被选定元素大的部分都去该元素的右边，所有比被选定元素小的部分都去该元素的左边。这样我

8、们就确定了该元素在这个待排序列中的位置，其实也就是我们已经将这个元素“排好了”。8 、详细设计和编码1 .冒泡排序：voidgensort(intb,intn)(inti,j;ints=0,t=0;for(i=0;i<n-1;i+)(for(j=i+1;j<n;j+)(t+;if(bi>bj)(inttemp=bi;bi=bj;bj=temp;s+=3;)cout<<"移动次数="<<s<<","<<"比较次数="<<t<<endl;2 .直接插

9、入排序：voidinsertsort(sqlistb,intn)(inti,j;ints=0,t=0;for(i=2;i<n;i+)(b0=bi;s+;j=i-1;t+;while(b0.key<bj.key)(bj+1=bj;j-;s+;t+;bj+1=b0;s+;cout<<"移动次数="<<s<<","<<"比较次数="<<t<<endl;3 .简单选择排序：voidgentsort(intb,intn)(inti,j,k;ints=0,t=0;

10、for(i=0;i<n-1;i+)(k=i;for(j=i+1;j<n;j+)(t+;if(bk>bj)k=j；)if(k!=i)inttemp=bk;bk=bi;bi=temp;s+=3;cout<<"移动次数="<<s<<","<<"比较次数="<<t<<endl;4 .希尔排序：voidshellsort(sqlistb,intn)inti,j,gap;recx;ints=0,t=0;gap=n/2;while(gap>0)for(i

11、=gap+1;i<n;i+)j=i-gap;while(j>0)t+;if(bj.key>bj+gap.key)x=bj;bj=bj+gap;bj+gap=x;j=j-gap;s+=3;elsej=0;gap=gapcout<<"移动次数="<<s<<","<<"比较次数="<<t<<endl;5 .堆排序：voidsift(sqlistr,ints,intm)intj;recx;x=rs;for(j=2*s;j<=m;j*=2)q+;if

12、(j<m&&(rj.key<rj+1.key)+j；q+；if(!(x.key<rj.key)break;rs=rj;s=j;p+;rs=x;p+;voidheapsort(sqlist&r,intm)inti;recw;for(i=m/2;i>0;-i)sift(r,i,m);for(i=m;i>1;-i)w=ri;ri=r1;r1=w;p+=3;sift(r,1,i-1);voidsorting(sqlist&r,intt)BeforeSort();heapsort(r,t);display(p,q);voidinit(inta

13、口儿随机生成N个整数并inti;srand(unsignedint)time(NULL);for(i=0;i<N;i+)ai=rand()%99+1;6 .归并排序：#include<stdio.h>voidcutTwo(intsourceArr,int*tempArr,intstart,intend);voidmerge(intsourceArr,int*tempArr,intstart,intmid,intend);intmain(intargc,char*argv)inta8=50,10,20,30,70,40,80,60;int*b8=);inti;cutTwo(a,

14、b,0,8);for(i=0;i<8;i+)printf("%d",ai);)return0;)/*归并排序算法：*/voidmerge(intsourceArr,int*tempArr,intstart,intmid,intend)/当前我们有一个源数组，我们在比较时将这个源数组一分为二进行比较归并排序/*因为我们要进行归并排序，所以我们需要两个指针分别指向两个子序列的开始位置，即start指向左边部分的开始位置，mid+1指向右边部分的开始位置，我们还需要一个k的下标，用于存储我们交换过来的数组到临时数组tempArr口*/inti=start;/定义一个i下标，

15、用于表示左边部分开始的位置下标intj=mid+1;/定义一个j下标，用于表示右边部分开始的位置下标intk=0;/*因为我们在比较时是不断的比较，直到一个子序列到达最后，所以我们应该用while循环来做，结束条件：无非就是左边序列到头了或者是右边序列到头了，即：i<=mid&&j<=end只有在这两个条件都成立的条件下说明两个子序列都没有到头*/while(i<=mid&&j<=end)/当i=mid+1或者j=end+1时说明子序列中有一个到头了，则跳出循环if(sourceArri<=sourceArrj)/表示当前i比较小，

16、那么我们就将小的值赋给ktempArrk=sourceArri;k=k+1;i=i+1;)elsetempArrk=sourceArrj;k=k+1;j=j+1;/*不能将k,i,j的加1操作放在ifelse判断的外面，因为我们在进行比较的时候，只是将下标所指的数字小的放在左边，将下标所指的数字大的不动，因为我们小的下标加1后还要和刚才下标所指的数字再次进行比较，如果放在外面，那么我们的比较的对象不对了(因为的大的数字的下标加1了，前面的一个数字没有进行比较)*/)/*当有一个子序列到头以后，我们就要将剩余没到头的子序列的剩余元素放到k的右边，因为剩余的肯定是已经有序的，且肯定比已经到头的子序

17、列的全部元素都要大的。*/while(j<=end)/i=mid+1&&因为左边序列i跳出循环的条件肯定是当前i=mid+1了，则我们移动右边j的子序列就好了tempArrk=sourceArrj;k+;j+;)while(i<=mid)/&&j=end+1则此时表示当前跳出循环的是j右边的子序列，则我们移动左边的i的子序列tempArrk=sourceArri;k+;i+;)intm;for(m=0;m<k;m+)sourceArrstart+m=tempArrm;)/*上述操作完成仅仅是完成了对一个大的序列中一部分的排列，因为我们的做法是对

18、整个的序列进行二分，二分之后对子序列进行归并排序*/voidcutTwo(intsourceArr,int*tempArr,intstart,intend)if(start<end)intmid;/设置一个取中间的变量mid=(start+end)/2;cutTwo(sourceArr,tempArr,start,mid);cutTwo(sourceArr,tempArr,mid+1,end);merge(sourceArr,tempArr,start,mid,end);7.快速排序：voidoutput(sqlistb,intn)/输出元素值for(inti=0;i<n;i+)c

19、out<<setw(4)<<bi.key;cout<<endl;voiddisplay(intn,intm)/输出计数cout<<"移动次数="<<n<<","<<"比较次数="<<m<<endl;voidBeforeSort()/初始化计数器p=0;q=0;voidquicksort(sqlistr,ints,intt)inti=s,j=t;if(s<t)r0=rs;p+;while(i<j)p+;while(i&

20、lt;j&&rj.key>=r0.key)j-;ri=rj;q+;p+;p+;while(i<j&&ri.key<=r0.key)i+;rj=ri;q+;p+;ri=r0;p+;elsereturn;quicksort(r,s,j-1);quicksort(r,j+1,t);)voidsort(sqlistr,ints,intt)(BeforeSort();quicksort(r,s,t);display(p,q);)4、上机调试过程编程过程中出现了各种各样的错误，如输错代码，未定义变量，数组下标越界，产生随机数据的程序不工作等等，导致编译没能

21、通过没有结果.最后和组员讨论，又请教一些同学，终于把所有问题都解决掉，运行出了结果.5、测试结果及其分析下图是自动产生的五组随机产生的100个数据的排序结果，由图可知希尔排序、快速排序的关键字移动次数和比较次数都相对较少。起泡排序、选择排序中关键字比较次数很大，起泡排序、插入排序移动次数很大。这样方便我们快捷的看出排序优缺点。苴|-|g|264G6377673186743376S43144419333554199&7473318518沔6642404633583622567785963366940916455664616651?376664日781852113226。99179135?

22、9319766364mE4*9326A9RX2sS2A1S5119a33R2。"C：,Doci»exi,t=<ukd$£<.七:an.6与Ad»i.m.:oz".ifi应1)/1>11后耳熟ex±-斤前数组:22254040767697”224Q6276?619277G?519366174531835G87473IB3EGB7371173G971123£586?89«-*-4:卜*一£鼻卜界H喙殳身匕导9:LL士UL士口1+口口匕士口七粕卜行19行福宁行屿仃8,结31-运Y运-2运力运=

23、2,造=4行=9殂序数序数序数序数序茗，数数扑江扑江具江挣认拌仪序代后泡动入动力动行速动彗序卷兽移选；"匚U&ersyangchun?e5ktcp',DebugCpple>?S834GE。79333G68422S33b414314352三*S92959髀耕疗运行结毛葭想以数会也/也粒次数=4入日拌房运彳亍结廨箍运行结臬：=2G2&f口J蜜次数T95g蠹疆,法勿，比较次数T国812912942943143914SIse21'C：U&e-5yangchu-ie$ktcpDebcigXCpple>?84243=54r窃冬粉制结3结Lilf

24、ssrt第果上泡夕勤小动彗速动曹咛-Tv-Tfl-J*-T2-J4n52彳3彳£/i5/i_s.162:运=b运=2运=1运-2运=5存T组序瞿瞽教序高新运图2""¥'-推妆抖除/蒙后数次34瑞27272£2938'C：U$er5yangchu-iWe$ktup3bugCppi?>e4iS18修5-，较，一校.:"飞，-I父*:"阳交ALruS,LU%S-ury-ny4vti结3,结E,结辑北露果上丁35-丁X丁i丁2二丁L吐口7彳2彳g彳74,-8/14-1:运=b运=2运=G运-2运=5存T组序数序

25、帛翻序器热运数数i排度斗."逃斗工序嫉后泡甘幼小动卷速动静拧20261478?643426b441:-盅盅欠,父-:次羽nMLruBLrumF.«ITury-ny4v-kfv-结氏结2,结雪北韵果上14J±1-T2-7s-Jt-J-5-T12彳3彳£彳8.58.-3:运=b运=2运=9运-2运=5HT组序修瞽整鳌新运图24遍.算高力斗工序亮后泡卞勤小动.速动曹咛起越通移祎IU选耳辕唯悼44UIuoS9'U&eyangchu-i?e?ktcpDebugCppie>?6、用户使用说明内部排序算法比较用户使用说明本系统采用VisualC+

26、遮言编写,运用软件工程的思想,采用面向对象分析、设计的方法学完成。本程序主要用于人们比较排序算法，从直观感受各种排序的优缺点。7、参考文献1严蔚敏，吴伟民.数据Z勾(C语言版)M.北京：清华大学出版社，1997.042严蔚敏，吴伟民.数据结本题集(C语言版)M.北京：清华大学出版社，1997.043汪杰等，数据结构经典算法实现与习题解答M.北京：人民邮电出版社，20044陈媛，何波，涂晓红等，算法与数据结构M.北京：清华大学出版社，20055李春葆.数据结构习题与解析(第二版)M.北京：清华大学出版社，2004.078、附录#include<iostream.h>#include&

27、lt;iomanip.h>#include<stdlib.h>#include<stdio.h>#include<time.h>#defineN100intp,q;/起泡排序voidgensort(intb,intn)inti,j;ints=0,t=0;for(i=0;i<n-1;i+)for(j=i+1;j<n;j+)t+;if(bi>bj)inttemp=bi;bi=bj;bj=temp;s+=3;cout<<"移动次数="<<s<<","<<

28、"比较次数="<<t<<endl;/插入排序typedefintKeyType;structrecKeyTypekey;typedefrecsqlistN;voidinsertsort(sqlistb,intn)(inti,j;ints=0,t=0;for(i=2;i<n;i+)(b0=bi;s+;j=i-1;t+;while(b0.key<bj.key)(bj+1=bj;j-;s+;t+;bj+1=b0;s+;cout<<"移动次数="<<s<<","<&

29、lt;"比较次数="<<t<<endl;/希尔排序voidshellsort(sqlistb,intn)(inti,j,gap;recx;ints=0,t=0;gap=n/2;while(gap>0)(for(i=gap+1;i<n;i+)(j=i-gap;while(j>0)(t+;if(bj.key>bj+gap.key)(x=bj;bj=bj+gap;bj+gap=x;j=j-gap;s+=3;elsej=0;gap=gap)cout«"移动次数="<<s«"

30、,"«"比较次数="«t«endl;/选择排序voidgentsort(intb,intn)(inti,j,k;ints=O,t=O;for(i=0;i<n-1;i+)(k=i;for(j=i+1;j<n;j+)(t+；if(bk>bj)k=j；)if(k!=i)inttemp=bk;bk=bi;bi=temp;s+=3;)cout«"移动次数="<<s«","«"比较次数="«t«endl;/快

31、速排序voidoutput(sqlistb,intn)/输出元素值(for(inti=0;i<n;i+)cout«setw(4)«bi.key;cout«endl;)voiddisplay(intn,intm)/输出计数cout«"移动次数="<<n«","«"比较次数="«m«endl;)voidBeforeSort()/初始化计数器p=O；q=0；)voidquicksort(sqlistr,ints,intt)(inti=s,j=t

32、;if(s<t)(r0=rs;p+;while(i<j)(p+;while(i<j&&rj.key>=r0.key)j-;ri=rj;q+;p+;p+;while(i<j&&ri.key<=r0.key)i+;rj=ri;q+;p+;)ri=r0;p+;)elsereturn;quicksort(r,s,j-1);quicksort(r,j+1,t);)voidsort(sqlistr,ints,intt)(BeforeSort();quicksort(r,s,t);display(p,q);)/堆排序voidsift(sqlistr,ints,intm)(intj;recx;x=r