幾種常見(jiàn)的排序算法的實(shí)現(xiàn)與性能分析數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告VIP

1、課程設(shè)計(jì)(論文)題 目 名 稱(chēng) 幾種常見(jiàn)的排序算法的實(shí)現(xiàn)與性能分析 課 程 名 稱(chēng) 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 學(xué) 生 姓 名 學(xué) 號(hào) 系 、專(zhuān) 業(yè) 信息工程系、通信工程 指 導(dǎo) 教 師 2012年 12 月 23 日 摘 要設(shè)計(jì)一個(gè)測(cè)試程序比較起泡排序、直接排序、簡(jiǎn)單選擇排序、快速排序、希爾排序、堆排序算法的關(guān)鍵字比較次數(shù)和移動(dòng)次數(shù)。運(yùn)用多種自定義函數(shù)，通過(guò)在主函數(shù)中調(diào)用自定義函數(shù)，實(shí)現(xiàn)其功能，最后輸出相應(yīng)算法的比較次數(shù)(至少有五種不同的數(shù)據(jù))和移動(dòng)次數(shù)（關(guān)鍵字的交換記為三次移動(dòng)）。從而直觀的判斷各內(nèi)部排序算法性能的優(yōu)劣性。關(guān)鍵詞：起泡排序；直接排序；簡(jiǎn)單選擇排序；快速排序；希爾排序；堆排序；內(nèi)部排序

2、；直觀；比較次數(shù)；移動(dòng)次數(shù) 目錄1 問(wèn)題描述12 需求分析13 概要設(shè)計(jì)131抽象數(shù)據(jù)類(lèi)型定義132模塊劃分24 詳細(xì)設(shè)計(jì)341數(shù)據(jù)類(lèi)型的定義342主要模塊的算法描述35 測(cè)試分析86 課程設(shè)計(jì)總結(jié)12參考文獻(xiàn)12附錄（源程序清單）131 問(wèn)題描述設(shè)計(jì)一個(gè)測(cè)試程序比較起泡排序、直接排序、簡(jiǎn)單選擇排序、快速排序、希爾排序、堆排序算法的關(guān)鍵字比較次數(shù)和移動(dòng)次數(shù)以取得直觀感受。待排序表的表長(zhǎng)不小于100，表中數(shù)據(jù)隨機(jī)產(chǎn)生，至少用5組不同數(shù)據(jù)作比較，比較指標(biāo)有：關(guān)鍵字參加比較次數(shù)和關(guān)鍵字的移動(dòng)次數(shù)（關(guān)鍵字交換記為3次移動(dòng)）。最后輸出比較結(jié)果。2 需求分析（1）用數(shù)組S來(lái)存放系統(tǒng)隨機(jī)產(chǎn)生的100個(gè)數(shù)據(jù)，

3、并放到R數(shù)組中，數(shù)據(jù)由程序隨機(jī)產(chǎn)生，用戶(hù)只需查看結(jié)果。（2）利用全局變量times和changes來(lái)分別統(tǒng)計(jì)起泡排序、直接排序、簡(jiǎn)單選擇排序、快速排序、希爾排序、堆排序算法的比較次數(shù)和移動(dòng)次數(shù)，然后輸出結(jié)果，并在每一次統(tǒng)計(jì)之后，將times和changes都賦值為0。（3）在主函數(shù)中調(diào)用用戶(hù)自定義函數(shù)，輸出比較結(jié)果。（4）本程序是對(duì)幾種內(nèi)部排序算法的關(guān)鍵字進(jìn)行性能分析的程序，它分為以下幾個(gè)部分：a、建立數(shù)組；b、調(diào)用函數(shù)求比較和移動(dòng)次數(shù)；c、輸出結(jié)果。3 概要設(shè)計(jì)31抽象數(shù)據(jù)類(lèi)型定義排序數(shù)據(jù)類(lèi)型定義：ADT paixu數(shù)據(jù)對(duì)象：D=aij|aij屬于1，2，3,i,j>0數(shù)據(jù)關(guān)系：R=&

4、lt;ai-1,ai>|ai-1,aiD，i=2,.,n基本操作：Insertsort();初始條件：數(shù)組已經(jīng)存在?；舅枷耄簩⒁粋€(gè)記錄插入到已經(jīng)排好序的有序列表中，從而得到了一個(gè)新的、記錄新增1的有序表。 Shellsort();初始條件：數(shù)組已經(jīng)存在?；舅枷耄合热《ㄒ粋€(gè)正整數(shù)d1<n,把全部記錄分成d1個(gè)組，所有距離為d1倍數(shù)的記錄放在一組中，在各組內(nèi)進(jìn)行插入排序，然后取d2<d1重復(fù)上述分組和排序工作，直至取di=1,即所有記錄放在一個(gè)組中排序?yàn)橹?。Bubblesort();初始條件：數(shù)組已經(jīng)存在?；舅枷耄簝蓛杀容^待排序記錄的鍵值，并交換不滿(mǎn)足順序要求的那些偶對(duì)，直

5、到全部滿(mǎn)足順序要求為止。QuickSort(int low,int high)；初始條件：數(shù)組已經(jīng)存在。基本思想：在待排序的n個(gè)記錄中任取一個(gè)記錄（通常取第一個(gè)記錄），以該記錄的鍵值為基準(zhǔn)用交換的方法將所有記錄分成兩部分，所有鍵值比它小的安置在一部分，所有鍵值比它大的安置在另一部分，并把該記錄排在兩部分的中間，也就是該記錄的最終位置。這個(gè)過(guò)程稱(chēng)為一趟快速排序。然后分別對(duì)所劃分的兩部分重復(fù)上述過(guò)程，一直重復(fù)到每部分內(nèi)只有一個(gè)記錄為止排序完成。Selectsort();初始條件：數(shù)組已經(jīng)存在。基本思想：每次從待排序的記錄中選出鍵值最?。ɑ蜃畲螅┑挠涗洠樞蚍旁谝雅判虻挠涗浶蛄械淖詈?，直到全部排完。

6、對(duì)待排序的文件進(jìn)行n-1趟掃描，第i趟掃描選出剩下的n-i+1個(gè)記錄，并與第i個(gè)記錄交換。 Heap();初始條件：數(shù)組已經(jīng)存在。基本思想：對(duì)一組待排序的的鍵值，首先是把它們按堆的定義排列成一個(gè)序列（稱(chēng)為初建堆），這就找到了最小鍵值，然后把最小的鍵值取出，用剩下的鍵值再重建堆，便得到次小鍵值，如此反復(fù)進(jìn)行，知道把全部鍵值排好序?yàn)橹埂DT 排序32模塊劃分本程序包括兩個(gè)模塊：（1）主程序模塊void main()初始化；隨機(jī)數(shù)的產(chǎn)生；調(diào)用子函數(shù)；（2）子函數(shù)模塊：實(shí)現(xiàn)直接插入排序的抽象數(shù)據(jù)類(lèi)型。 實(shí)現(xiàn)希爾排序的抽象數(shù)據(jù)類(lèi)型。 實(shí)現(xiàn)冒泡排序的抽象數(shù)據(jù)類(lèi)型。 實(shí)現(xiàn)快速排序的抽象數(shù)據(jù)類(lèi)型。 實(shí)現(xiàn)選擇

7、排序的抽象數(shù)據(jù)類(lèi)型。 實(shí)現(xiàn)堆排序的抽象數(shù)據(jù)類(lèi)型。最后輸出相應(yīng)算法的比較次數(shù)(至少有五種不同的數(shù)據(jù))和移動(dòng)次數(shù)（關(guān)鍵字的交換記為三次移動(dòng)）。從而直觀的判斷各內(nèi)部排序算法性能的優(yōu)劣性。4 詳細(xì)設(shè)計(jì)41數(shù)據(jù)類(lèi)型的定義(1)直接插入排序類(lèi)型：void Insertsort();(2)希爾排序類(lèi)型：void Shellsort();(3)冒泡排序類(lèi)型：void Bubblesort();(4)快速排序類(lèi)型：void QuickSort(int low,int high);(5)選擇排序類(lèi)型：void Selectsort();(6)堆排序類(lèi)型：void Heap();42主要模塊的算法描述下面是主程序的

8、結(jié)構(gòu)圖和幾個(gè)主要模塊的流程圖：開(kāi)始 循環(huán)產(chǎn)生一組隨機(jī)數(shù)將隨機(jī)數(shù)保存在數(shù)組中堆排序選擇排序快速排序起泡排序希爾排序插入排序記錄關(guān)鍵字的比較次數(shù)和移動(dòng)次數(shù)輸出關(guān)鍵字的比較次數(shù)和移動(dòng)次數(shù)結(jié)束 4.21主程序結(jié)構(gòu)圖 開(kāi)始輸入要排序的一組元素i=1,j=1定義臨時(shí)中間變量k，并賦初值i<元素總個(gè)數(shù) N i<i+1j<元素總個(gè)數(shù) N Y j=j+1第j個(gè)元素>第j+1個(gè)元素 Y N利用k交換第j個(gè)元素和第j+1個(gè)元素 Y輸出比較次數(shù)和移動(dòng)次數(shù)結(jié)束 4.22冒泡排序關(guān)鍵字比較次數(shù)和移動(dòng)次數(shù)的流程圖開(kāi)始輸入要排序的一組元素i=1，j=1定義臨時(shí)中間變量h，并賦初值i<元數(shù)總個(gè)數(shù)

9、N做第i趟排序 Yi=i+1在無(wú)序區(qū)Ri-n中選h最小記錄Rhh記下目前找到的最小關(guān)鍵字所在的位置交換Ri和Rh輸出比較次數(shù)和移動(dòng)次數(shù)結(jié)束 4.23選擇排序關(guān)鍵字比較次數(shù)和移動(dòng)次數(shù)的流程圖開(kāi)始輸入要排序的一組元素定義臨時(shí)中間變量k，并賦初值將二叉樹(shù)轉(zhuǎn)換成堆i=總元素個(gè)數(shù)-1i<=1 N將堆的根植和最后一個(gè)值交換 Yi-,k+輸出比較次數(shù)和移動(dòng)次數(shù)結(jié)束4.24堆排序關(guān)鍵字比較次數(shù)和移動(dòng)次數(shù)的流程圖5 測(cè)試分析進(jìn)行了99趟排序后，得到了最終的排序結(jié)果，并且也知道了直接插入排序的比較次數(shù)和移動(dòng)次數(shù)了解了直接插入排序的性能后，下面是希爾排序的性能比較：了解了希爾排序的性能后，下面是冒泡排序的性能

10、比較：了解了冒泡排序的性能后，下面是快速排序的性能比較：了解了快速排序的性能后，下面是選擇排序的性能比較：了解了選擇排序的性能后，下面是堆排序的性能比較：以上就是對(duì)六種排序算法的一種演示，經(jīng)過(guò)觀察和分析我們可以比較六種排序的性能。6 課程設(shè)計(jì)總結(jié)通過(guò)本次課程設(shè)計(jì)，我對(duì)直接插入排序，希爾排序，選擇排序等六種排序的概念有了一個(gè)新的認(rèn)識(shí)，也慢慢地體會(huì)到了它們之間的奧妙。這次的課程設(shè)計(jì)，加強(qiáng)了我的動(dòng)手，思考和解決問(wèn)題的能力。鞏固和加深了我對(duì)數(shù)據(jù)結(jié)構(gòu)的理解，也讓我懂得了理論與實(shí)際相結(jié)合是非常重要的，更讓我進(jìn)一步明白了“團(tuán)結(jié)就是力量”這句話(huà)的含義。在整個(gè)設(shè)計(jì)過(guò)程中，構(gòu)思是很花時(shí)間的。調(diào)試時(shí)經(jīng)常會(huì)遇到這樣那

11、樣的錯(cuò)誤，有的是因?yàn)榇中脑斐傻恼Z(yǔ)法錯(cuò)誤。當(dāng)然，很多是因?yàn)橛缅e(cuò)了方法，總是實(shí)現(xiàn)不了。同時(shí)在設(shè)計(jì)過(guò)程中發(fā)現(xiàn)了自己的不足之處，對(duì)以前所學(xué)過(guò)的知識(shí)理解的不夠深刻，掌握的不夠透徹。根據(jù)我在課程設(shè)計(jì)中遇到的問(wèn)題，我將在以后的學(xué)習(xí)過(guò)程中注意以下幾點(diǎn)：1、多在實(shí)踐中鍛煉自己；2、寫(xiě)程序的過(guò)程中要考慮周到；3、在做設(shè)計(jì)的時(shí)候要有信心，有耐心，切勿浮躁。此次的課程設(shè)計(jì)得以順利完成，與黃同成老師的耐心指導(dǎo)和同學(xué)們的及時(shí)幫助是分不開(kāi)的。當(dāng)我在編寫(xiě)程序遇到難題時(shí)，是黃老師的耐心指導(dǎo)，我才可以突破一個(gè)個(gè)難關(guān)。在程序設(shè)計(jì)過(guò)程中，同學(xué)們給我的鼓勵(lì)和幫助使我信心倍增。在此我再次向黃同成老師和熱心幫助我的同學(xué)表示深深的謝意。參考

12、文獻(xiàn)1 黃同成，黃俊民，董建寅數(shù)據(jù)結(jié)構(gòu)M北京：中國(guó)電力出版社，20082 董建寅，黃俊民，黃同成數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)與題解M北京：中國(guó)電力出版社，20083 嚴(yán)蔚敏，吳偉民. 數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）M. 北京：清華大學(xué)出版社，20024 劉振鵬，張曉莉，郝杰數(shù)據(jù)結(jié)構(gòu)M北京：中國(guó)鐵道出版社，2003 附錄（源程序清單）#include <stdio.h>#include <stdlib.h>#include <math.h>#include <time.h>#define L 100#define FALSE 0#define TRUE 1/*typed

13、ef structint key;char otherinfo;RecType;*/typedef RecType SeqlistL+1;int s100,R100;int num;int times=0,changes=0;/Seqlist R;void Insertsort();void Bubblesort();void QuickSort(int low,int high);void Shellsort();void Selectsort();void Heap();int Partition();void main()/Seqlist S;int i,k;char ch1,ch2,q

14、;printf("產(chǎn)生100個(gè)隨機(jī)數(shù)：n"); srand(unsigned)time(NULL); for(i=1;i<=L;i+) si=rand()%100; for(i=1;i<=L;i+) printf("%4d",si); printf("nt排序數(shù)據(jù)已經(jīng)輸入完畢！"); for(i=1;i<=L;i+)Ri=si; ch1='y'while (ch1='y'|ch1='Y')printf("nnnnnttt排 序 性 能 分 析n");

15、 printf("tt*n"); printf("tt* 1-直接插入排序 -*n"); printf("tt* 2-希 爾 排 序 -*n"); printf("tt* 3-冒 泡 排 序 -*n"); printf("tt* 4-快 速 排 序-*n"); printf("tt* 5-選 擇 排 序 -*n"); printf("tt* 6-堆 排 序-*n"); printf("tt* 0-返 回-*n"); printf(&qu

16、ot;tt*n"); printf("tt請(qǐng)選擇菜單號(hào)（0-6）:");scanf("%c",&ch2);getchar();for(i=1;i<=L;i+)Ri=si;switch(ch2)case '1':Insertsort();break;case '2':Shellsort();break;case '3':Bubblesort();break; case '4': printf("ntt尚未排序的數(shù)據(jù)為（回車(chē)?yán)^續(xù)）："); for(k=

17、1;k<=L;k+) printf("%5d",Rk); getchar();printf("n"); num=0;QuickSort(1,L); break;case '5':Selectsort();break; case '6':Heap();break;case '0':ch1='n'break;default:printf("tt輸入錯(cuò)誤！請(qǐng)重新輸入！ntt");if(ch2!='0')if(ch2='2'|ch2='

18、;3'|ch2='4'|ch2='5'|ch2='6'|ch2='7'|ch2='8')printf("nt排序演示輸出完畢！n"); printf("nt請(qǐng)按回車(chē)鍵返回主菜單.");q=getchar();if (q!='xA') getchar();ch1='n'void Insertsort()/直接插入排序int i,j,k,m=0; printf("ntt尚未排序的數(shù)據(jù)為（回車(chē)?yán)^續(xù)）：");for(k=1;

19、k<=L;k+)printf("%5d",Rk);getchar();printf("n");for(i=2;i<=L;i+)if(Ri<Ri-1) R0=Ri;j=i-1;while(R0<Rj) times+; changes+;Rj+1=Rj;j-;Rj+1=R0; changes+;m+; times+;printf("nn"); printf("t最終排序結(jié)果為：");for(i=1;i<=L;i+)printf("%5d",Ri);printf(&quo

20、t;n"); printf("nt直接插入排序的比較次數(shù)為%d",times); printf("nt直接插入排序的移動(dòng)次數(shù)為%d",changes); times=0; changes=0;void Shellsort() /希爾排序int i,j,gap,x,m=0,k; printf("nt尚未排序的數(shù)據(jù)為（回車(chē)?yán)^續(xù)）："); for(k=1;k<=L;k+)printf("%5d",Rk);getchar();printf("n");gap=L/2;while (gap&

21、gt;0)for(i=gap+1;i<=L;i+) j=i-gap;while(j>0) times+;if (Rj>Rj+gap)x=Rj;Rj=Rj+gap;Rj+gap=x;j=j-gap; changes+; elsej=0;gap=gap/2;m+;printf("nn"); printf("t最終排序結(jié)果為：");for(i=1;i<=L;i+)printf("%5d",Ri);printf("n"); printf("nt希爾排序的比較次數(shù)為%d",time

22、s); printf("nt希爾排序的移動(dòng)次數(shù)為%d",changes); times=0; changes=0;void Bubblesort()/冒泡排序int i,j,k; int exchange; printf("ntt尚未排序的數(shù)據(jù)為（回車(chē)?yán)^續(xù)）：");for(k=1;k<=L;k+)printf("%5d",Rk);getchar();printf("n");for(i=1;i<=L;i+)exchange=FALSE;for(j=L;j>=i+1;j-) times+; if(Rj

23、<Rj-1) R0=Rj; Rj=Rj-1; Rj-1=R0; exchange=TRUE; changes+=3;if(exchange); printf("nn"); printf("t最終排序結(jié)果為：");for(i=1;i<=L;i+)printf("%5d",Ri);printf("n"); printf("nt冒泡排序的比較次數(shù)為%d",times); printf("nt冒泡排序的移動(dòng)次數(shù)為%d",changes); times=0; changes

24、=0;int Partition(int i,int j) /快速排序int pirot=Ri;while(i<j)while(i<j&&Rj>=pirot)j-; times+;if(i<j)Ri+=Rj; changes+;while(i<j&&Ri<=pirot)i+; times+;if(i<j)Rj-=Ri; changes+;Ri=pirot;return i;void QuickSort(int low,int high)int pirotpos,k,i;if (low<high)pirotpos=P

25、artition(low,high);num+;QuickSort(low,pirotpos-1); QuickSort(pirotpos+1,high);printf("nn"); printf("t最終排序結(jié)果為：n");for(i=1;i<=L;i+)printf("%5d",Ri);printf("n");printf("nt快速排序的比較次數(shù)為%d",times);printf("nt快速排序的移動(dòng)次數(shù)為%d",changes);times=0;changes

26、=0;void Selectsort() /選擇排序int i,j,k,h; printf("ntt尚未排序的數(shù)據(jù)為（回車(chē)?yán)^續(xù)）：");for(k=1;k<=L;k+)printf("%5d",Rk);getchar();printf("n");for(i=1;i<=L;i+) h=i;for(j=i+1;j<=L;j+)times+; if (Rj<Rh)h=j;if(h!=j)R0=Rh;Rh=Ri;Ri=R0; changes+=3; printf("nn"); printf("t最終排序結(jié)果為：");for(i=1;i<=L;i+)printf("%5d",Ri);printf("n"); printf("nt選擇排序的比較次數(shù)為%d",times); prin