数据结构：简单选择,直接插入,快速排序,冒泡排序希尔排序,堆排序算法比较平台.docx

《数据结构：简单选择,直接插入,快速排序,冒泡排序希尔排序,堆排序算法比较平台.docx》由会员分享，可在线阅读，更多相关《数据结构：简单选择,直接插入,快速排序,冒泡排序希尔排序,堆排序算法比较平台.docx（18页珍藏版）》请在优知文库上搜索。

1、一、试验内容内部排序算法效率比较平台的设计与实现二、试验目的问题描述：各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机的数据比较几种主要的基本算法的关键字比较次数和关键字移动次数，以取得直观感受。f开始J三、流程图冒泡排序J-N-I简单选择排序直接插入排序开始-2假K=LIenqt1.r.keyuAImFLrW；1.r()=L(l:j=i-2；假1.rGkeyL.r113，真1.foF=L而;1.mTJ=Lr+i结束希尔排序开始k=0假kkfljkLidk.jO&lf0.kpvlr(lk0A1.rj*dk=Lrj.j-d；1.rj*dk=lr(O)i+k

2、结灾快速排序四、源程序代码ftdefineN10intComPare6=0,0,0,0,0,0,Change6=0,0,0,0,0,0;voidinput(ints)(inttestN;srand(unsigned)time(NULL);for(inti=O;iN;i+)testi=rand()%100;for(intj=O;ji;j+)while(testj=testi)(testi=rand()%N;j=O;)for(i=0;i=N-l;i+)si=testi;)voidswap(int&a,int&b)(inttmp;tmp=a;a=b;b=tmp;)voidinsertsort(int

3、s)(inti,j;intaN+l;ai=si-l;)for(i=2;i0&a0aj-l&(+compare0);j-)(aU=O-l;changeO+;)aU=aO;changeO+;)voidbubble_sort(ints,intn)(inti,j,temp,aN;for(i=0;in;i+)(ai=si;)for(j=0;jaj+l)(temp=aj;a11=aU+l;a+l=temp;changel+;)intpartition(intaJntIowJnthigh)(inttzky;t=alow;key=alow;while(lowhigh)(while(low=key)(high-

4、;+compare2;if(lowhigh)(alow=ahigh;low+;change2+;)while(lowhigh&alow=key)(low+;+compare2;)if(lowhigh)(ahigh=alow;high-;change2+;)alow=t;)returnlow;)voidquicksort(intaJntIowJnthigh)intkey;if(lowhigh)(key=partition(a,lowzhigh);quicksort(a,low,key-1);quicksort(a,key+lzhigh);)voidselectsort(intszintn)(in

5、ti,j,k,aN;intt;for(i=0;in;i+)(a=si;)for(i=0;in-l;i+)(j=i；for(k=i+l;k=n-l;k+)(if(akaj&(+compare3)j=k;if(j!=i)t=ai;ai=aU;aj=t;change3+;)voidshellinsertsort(intsJntn)(intizk,aN;k=int(n2);for(i=0;i0;gap/=2)(for(inti=gap;i0&atmpaj-gap;j-=gap)aUl=aU-gap;compare4+;)aj=tmp;change4+;)voidheap_adjust(intarray

6、,inti,intlen)(intrc=arrayi;for(intj=2*i;jlen;j*=2)(if(jIen&arrayj=arrayj)break;)arrayi=arrayj;i=j;)arrayi=rc;)voidheap_sort(intaJntlen)inti;for(i=(len-l)2;i=0;i-)heap_adjust(ajjen);for(i=(Ien-I);i0;i-)(swap(a0,ai);Change5+;弹出最大值，重新对i-1个元素建堆heap-adjust(azOzi-l);)voidCMyDIg-OnButtonlO(/TODO:Addyourcon

7、trolnotificationhandlercodehereUpdateData(TRUE);ints10,a10;input(s);for(inti=O;iN;i+)(ai=si;)CStringstr100;for(i=0;i100;i+)stri=ai;stri.FOrmatr%ij,ai);把整型数组添加到字符串m-shujul+=stri;)insertsort(s);m_zhijiel=compare0;m-zhijie2=change0;quicksort(azOzN-l);m-kuaisul=compare2;m_kuaisu2=change2;selectsort(sfN)

8、;mjiandanl=compare3;mjianda2=change3;SheIIinsertsort(SzN);m-xierl=compare4;m_xier2=change4;heap-sort(azN);m-duil=compare5;m-di2=change5;bubble_sort(s,N);m_maopaol=comparel;m-maopao2=changel;CStringstr2100;for(i=0;i100;i+)str2i=si;for(i=0;iN;i+)(str2i.Format(%iai);把整型数组添加到字符串m-shuju2+=str2i;)UpdateData(FALSE);)五、调试过程对于算法的设计，除了希尔排序和堆排序之外，都比较简单，要注意每种排序的起始位置和哨兵的位置，便可以正确的排出。而希尔排序，尽管是直接插入排序的变形，但应该从中间位置开始，从后至前选择，但是在程序上不好编出。而堆排序，更是难以控制，只好借鉴参考。六、结果分析由随机数产生的10个数，排序后的结果如上图所示，可以发现，快速排序和简单选择排序比较次数和交换次数均较少，适合使用。