幾種常見的排序算法的實現(xiàn)與性能分析數(shù)據結構課程設計報告

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

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

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

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

5、到全部滿足順序要求為止。QuickSort(int low,int high)；初始條件：數(shù)組已經存在?；舅枷耄涸诖判虻膎個記錄中任取一個記錄（通常取第一個記錄），以該記錄的鍵值為基準用交換的方法將所有記錄分成兩部分，所有鍵值比它小的安置在一部分，所有鍵值比它大的安置在另一部分，并把該記錄排在兩部分的中間，也就是該記錄的最終位置。這個過程稱為一趟快速排序。然后分別對所劃分的兩部分重復上述過程，一直重復到每部分內只有一個記錄為止排序完成。Selectsort();初始條件：數(shù)組已經存在?；舅枷耄好看螐拇判虻挠涗浿羞x出鍵值最小（或最大）的記錄，順序放在已排序的記錄序列的最后，直到全部排完。

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

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

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

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

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

11、樣的錯誤，有的是因為粗心造成的語法錯誤。當然，很多是因為用錯了方法，總是實現(xiàn)不了。同時在設計過程中發(fā)現(xiàn)了自己的不足之處，對以前所學過的知識理解的不夠深刻，掌握的不夠透徹。根據我在課程設計中遇到的問題，我將在以后的學習過程中注意以下幾點：1、多在實踐中鍛煉自己；2、寫程序的過程中要考慮周到；3、在做設計的時候要有信心，有耐心，切勿浮躁。此次的課程設計得以順利完成，與黃同成老師的耐心指導和同學們的及時幫助是分不開的。當我在編寫程序遇到難題時，是黃老師的耐心指導，我才可以突破一個個難關。在程序設計過程中，同學們給我的鼓勵和幫助使我信心倍增。在此我再次向黃同成老師和熱心幫助我的同學表示深深的謝意。參考

12、文獻1 黃同成，黃俊民，董建寅數(shù)據結構M北京：中國電力出版社，20082 董建寅，黃俊民，黃同成數(shù)據結構實驗指導與題解M北京：中國電力出版社，20083 嚴蔚敏，吳偉民. 數(shù)據結構（C語言版）M. 北京：清華大學出版社，20024 劉振鵬，張曉莉，郝杰數(shù)據結構M北京：中國鐵道出版社，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("產生100個隨機數(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ù)據已經輸入完畢！"); 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請選擇菜單號（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ù)據為（回車繼續(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輸入錯誤！請重新輸入！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=getchar();if (q!='xA') getchar();ch1='n'void Insertsort()/直接插入排序int i,j,k,m=0; printf("ntt尚未排序的數(shù)據為（回車繼續(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最終排序結果為：");for(i=1;i<=L;i+)printf("%5d",Ri);printf(&quo

20、t;n"); printf("nt直接插入排序的比較次數(shù)為%d",times); printf("nt直接插入排序的移動次數(shù)為%d",changes); times=0; changes=0;void Shellsort() /希爾排序int i,j,gap,x,m=0,k; printf("nt尚未排序的數(shù)據為（回車繼續(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最終排序結果為：");for(i=1;i<=L;i+)printf("%5d",Ri);printf("n"); printf("nt希爾排序的比較次數(shù)為%d",time

22、s); printf("nt希爾排序的移動次數(shù)為%d",changes); times=0; changes=0;void Bubblesort()/冒泡排序int i,j,k; int exchange; printf("ntt尚未排序的數(shù)據為（回車繼續(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最終排序結果為：");for(i=1;i<=L;i+)printf("%5d",Ri);printf("n"); printf("nt冒泡排序的比較次數(shù)為%d",times); printf("nt冒泡排序的移動次數(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最終排序結果為：n");for(i=1;i<=L;i+)printf("%5d",Ri);printf("n");printf("nt快速排序的比較次數(shù)為%d",times);printf("nt快速排序的移動次數(shù)為%d",changes);times=0;changes

26、=0;void Selectsort() /選擇排序int i,j,k,h; printf("ntt尚未排序的數(shù)據為（回車繼續(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最終排序結果為：");for(i=1;i<=L;i+)printf("%5d",Ri);printf("n"); printf("nt選擇排序的比較次數(shù)為%d",times); prin