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

1、課程設(shè)計(jì)(論文)題 目 名 稱 幾種常見的排序算法的實(shí)現(xiàn)與性能分析 課 程 名 稱 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 學(xué) 生 姓 名 學(xué) 號(hào) 系 、專 業(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ù)類型定義132模塊劃分24 詳細(xì)設(shè)計(jì)341數(shù)據(jù)類型的定義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)生，用戶只需查看結(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)用用戶自定義函數(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ù)類型定義排序數(shù)據(jù)類型定義：ADT paixu數(shù)據(jù)對(duì)象：D=aij|aij屬于1，2，3,i,j0數(shù)據(jù)關(guān)系：R=|ai-1

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

5、ow,int high)；初始條件：數(shù)組已經(jīng)存在。基本思想：在待排序的n個(gè)記錄中任取一個(gè)記錄（通常取第一個(gè)記錄），以該記錄的鍵值為基準(zhǔn)用交換的方法將所有記錄分成兩部分，所有鍵值比它小的安置在一部分，所有鍵值比它大的安置在另一部分，并把該記錄排在兩部分的中間，也就是該記錄的最終位置。這個(gè)過(guò)程稱為一趟快速排序。然后分別對(duì)所劃分的兩部分重復(fù)上述過(guò)程，一直重復(fù)到每部分內(nèi)只有一個(gè)記錄為止排序完成。Selectsort();初始條件：數(shù)組已經(jīng)存在?；舅枷耄好看螐拇判虻挠涗浿羞x出鍵值最小（或最大）的記錄，順序放在已排序的記錄序列的最后，直到全部排完。對(duì)待排序的文件進(jìn)行n-1趟掃描，第i趟掃描選出剩下的n

6、-i+1個(gè)記錄，并與第i個(gè)記錄交換。 Heap();初始條件：數(shù)組已經(jīng)存在?；舅枷耄簩?duì)一組待排序的的鍵值，首先是把它們按堆的定義排列成一個(gè)序列（稱為初建堆），這就找到了最小鍵值，然后把最小的鍵值取出，用剩下的鍵值再重建堆，便得到次小鍵值，如此反復(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ù)類型。 實(shí)現(xiàn)希爾排序的抽象數(shù)據(jù)類型。 實(shí)現(xiàn)冒泡排序的抽象數(shù)據(jù)類型。 實(shí)現(xiàn)快速排序的抽象數(shù)據(jù)類型。 實(shí)現(xiàn)選擇排序的抽象數(shù)據(jù)類型。 實(shí)現(xiàn)堆排序的抽象數(shù)據(jù)類型。最后輸

7、出相應(yīng)算法的比較次數(shù)(至少有五種不同的數(shù)據(jù))和移動(dòng)次數(shù)（關(guān)鍵字的交換記為三次移動(dòng)）。從而直觀的判斷各內(nèi)部排序算法性能的優(yōu)劣性。4 詳細(xì)設(shè)計(jì)41數(shù)據(jù)類型的定義(1)直接插入排序類型：void Insertsort();(2)希爾排序類型：void Shellsort();(3)冒泡排序類型：void Bubblesort();(4)快速排序類型：void QuickSort(int low,int high);(5)選擇排序類型：void Selectsort();(6)堆排序類型：void Heap();42主要模塊的算法描述下面是主程序的結(jié)構(gòu)圖和幾個(gè)主要模塊的流程圖：開始 循環(huán)產(chǎn)生一組隨機(jī)數(shù)

8、將隨機(jī)數(shù)保存在數(shù)組中堆排序選擇排序快速排序起泡排序希爾排序插入排序記錄關(guān)鍵字的比較次數(shù)和移動(dòng)次數(shù)輸出關(guān)鍵字的比較次數(shù)和移動(dòng)次數(shù)結(jié)束 4.21主程序結(jié)構(gòu)圖 開始輸入要排序的一組元素i=1,j=1定義臨時(shí)中間變量k，并賦初值i元素總個(gè)數(shù) N ii+1j第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ù)的流程圖開始輸入要排序的一組元素i=1，j=1定義臨時(shí)中間變量h，并賦初值i元數(shù)總個(gè)數(shù) N做第i趟排序 Yi=i+1在無(wú)序區(qū)Ri-n中選h最小記錄Rhh記下目前找到的最小關(guān)鍵字所在的位置交換Ri和Rh輸出比較次數(shù)和移動(dòng)次數(shù)

9、結(jié)束 4.23選擇排序關(guān)鍵字比較次數(shù)和移動(dòng)次數(shù)的流程圖開始輸入要排序的一組元素定義臨時(shí)中間變量k，并賦初值將二叉樹轉(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é)就是力量”這句話的含義。在整個(gè)設(shè)計(jì)過(guò)程中，構(gòu)思是很花時(shí)間的。調(diào)試時(shí)經(jīng)常會(huì)遇到這樣那樣的錯(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í)理解

11、的不夠深刻，掌握的不夠透徹。根據(jù)我在課程設(shè)計(jì)中遇到的問(wèn)題，我將在以后的學(xué)習(xí)過(guò)程中注意以下幾點(diǎn)：1、多在實(shí)踐中鍛煉自己；2、寫程序的過(guò)程中要考慮周到；3、在做設(shè)計(jì)的時(shí)候要有信心，有耐心，切勿浮躁。此次的課程設(shè)計(jì)得以順利完成，與黃同成老師的耐心指導(dǎo)和同學(xué)們的及時(shí)幫助是分不開的。當(dāng)我在編寫程序遇到難題時(shí)，是黃老師的耐心指導(dǎo)，我才可以突破一個(gè)個(gè)難關(guān)。在程序設(shè)計(jì)過(guò)程中，同學(xué)們給我的鼓勵(lì)和幫助使我信心倍增。在此我再次向黃同成老師和熱心幫助我的同學(xué)表示深深的謝意。參考文獻(xiàn)1 黃同成，黃俊民，董建寅數(shù)據(jù)結(jié)構(gòu)M北京：中國(guó)電力出版社，20082 董建寅，黃俊民，黃同成數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)與題解M北京：中國(guó)電力出版社，

12、20083 嚴(yán)蔚敏，吳偉民. 數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）M. 北京：清華大學(xué)出版社，20024 劉振鵬，張曉莉，郝杰數(shù)據(jù)結(jié)構(gòu)M北京：中國(guó)鐵道出版社，2003 附錄（源程序清單）#include #include #include #include #define L 100#define FALSE 0#define TRUE 1/*typedef structint key;char otherinfo;RecType;*/typedef RecType SeqlistL+1;int s100,R100;int num;int times=0,changes=0;/Seqlist R;void I

13、nsertsort();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;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)輸入完

14、畢！); for(i=1;i=L;i+)Ri=si; ch1=y;while (ch1=y|ch1=Y)printf(nnnnnttt排 序 性 能 分 析n); 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(tt*n); printf(tt請(qǐng)選

15、擇菜單號(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ù)為（回車?yán)^續(xù)）：); for(k=1;k=L;k+) printf(%5d,Rk); getchar();printf(n); num=0;QuickSort(1,L); break;case 5:Selectsort();break; case 6:He

16、ap();break;case 0:ch1=n;break;default:printf(tt輸入錯(cuò)誤！請(qǐng)重新輸入！ntt);if(ch2!=0)if(ch2=2|ch2=3|ch2=4|ch2=5|ch2=6|ch2=7|ch2=8)printf(nt排序演示輸出完畢！n); printf(nt請(qǐng)按回車鍵返回主菜單.);q=getchar();if (q!=xA) getchar();ch1=n;void Insertsort()/直接插入排序int i,j,k,m=0; printf(ntt尚未排序的數(shù)據(jù)為（回車?yán)^續(xù)）：);for(k=1;k=L;k+)printf(%5d,Rk);get

17、char();printf(n);for(i=2;i=L;i+)if(RiRi-1) R0=Ri;j=i-1;while(R0Rj) 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(n); printf(nt直接插入排序的比較次數(shù)為%d,times); printf(nt直接插入排序的移動(dòng)次數(shù)為%d,changes); times=0; changes=0;void Shellsort() /希爾

18、排序int i,j,gap,x,m=0,k; printf(nt尚未排序的數(shù)據(jù)為（回車?yán)^續(xù)）：); for(k=1;k0)for(i=gap+1;i0) times+;if (RjRj+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,times); printf(nt希爾排序的移動(dòng)次數(shù)為%d,changes); times=

19、0; changes=0;void Bubblesort()/冒泡排序int i,j,k; int exchange; printf(ntt尚未排序的數(shù)據(jù)為（回車?yán)^續(xù)）：);for(k=1;k=L;k+)printf(%5d,Rk);getchar();printf(n);for(i=1;i=i+1;j-) times+; if(RjRj-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);p

20、rintf(n); printf(nt冒泡排序的比較次數(shù)為%d,times); printf(nt冒泡排序的移動(dòng)次數(shù)為%d,changes); times=0; changes=0;int Partition(int i,int j) /快速排序int pirot=Ri;while(ij)while(i=pirot)j-; times+;if(ij)Ri+=Rj; changes+;while(ij&Ri=pirot)i+; times+;if(ij)Rj-=Ri; changes+;Ri=pirot;return i;void QuickSort(int low,int high)int p

21、irotpos,k,i;if (lowhigh)pirotpos=Partition(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=0;void Selectsort() /選擇排序int i,j,k,h; printf(ntt尚未排序的數(shù)據(jù)為（回車?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 (RjRh)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); pr