內(nèi)部排序算法的性能分析

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告設(shè)計(jì)題目：內(nèi)部排序算法的性能分析 專 業(yè) 通信工程 班 級(jí) 0803 學(xué) 生 潘志威 學(xué) 號(hào) 2008115020312 指導(dǎo)教師 孫玉霞 起止時(shí)間 2011-2-212011-2-27 湖北師范學(xué)院 2011 年 第一 學(xué)期目錄1需求分析21.1、選題要求21.2、選題的意義及背景21.3、課程設(shè)計(jì)目標(biāo)32概要設(shè)計(jì)32.1原始數(shù)據(jù)32.2輸出數(shù)據(jù)32.3數(shù)據(jù)處理43 算法描述53.1邏輯結(jié)構(gòu)及存儲(chǔ)結(jié)構(gòu)53.2系統(tǒng)的模塊劃分及模塊功能53.2.1主程序模塊53.2.2可排序表單元模塊63.3程序代碼64 調(diào)試分析15 測(cè)試結(jié)果25.1測(cè)試用例及選擇原因25.2 測(cè)試結(jié)果35

2、.3 結(jié)論35.4 結(jié)果分析36 心得體會(huì)47 參考文獻(xiàn)51需求分析1.1、選題要求對(duì)各種排序算法進(jìn)行定量的性能分析。1.2、選題的意義及背景排序是計(jì)算機(jī)程序設(shè)計(jì)中的一種重要操作。它的功能是將一個(gè)數(shù)據(jù)元素的任意序列，重新排列成一個(gè)按關(guān)鍵字有序的序列。內(nèi)部排序的方法很多，但是就其全面性能而言，很難提出一種被認(rèn)為是最好的方法，每一種方法都有各自的優(yōu)缺點(diǎn)，適合在不同的環(huán)境下使用。如果按排序過(guò)程中依據(jù)的不同原則對(duì)內(nèi)部排序方法進(jìn)行分類，則大致可分為插入排序，交換排序，選擇排序，歸并排序和記數(shù)排序等五類。此實(shí)驗(yàn)通過(guò)對(duì)起泡排序、直插排序、選擇排序、快速排序、歸并排序這幾種內(nèi)部排序算法進(jìn)行比較，能使我們更好的

3、掌握這些排序的基本思想及排序算法。通過(guò)該題目的設(shè)計(jì)過(guò)程，可以加深理解各種數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及相應(yīng)上運(yùn)算的實(shí)現(xiàn)，進(jìn)一步理解和熟練掌握課本中所學(xué)的各種數(shù)據(jù)結(jié)構(gòu)，學(xué)會(huì)如何把學(xué)到的知識(shí)用于解決實(shí)際問(wèn)題，培養(yǎng)我們的動(dòng)手能力。1.3、課程設(shè)計(jì)目標(biāo)本課程設(shè)計(jì)對(duì)以下內(nèi)部排序算法進(jìn)行比較：起泡排序、直插排序、選擇排序、快速排序、堆排序。待排序表的元素關(guān)鍵字為整數(shù)，用不同的測(cè)試數(shù)據(jù)做測(cè)試比較。比較的指標(biāo)為關(guān)鍵字的比較次數(shù)和關(guān)鍵字的移動(dòng)次數(shù)。最后用圖、表格數(shù)據(jù)匯總數(shù)據(jù)，以便對(duì)這些內(nèi)部排序算法進(jìn)行性能分析。 2概要設(shè)計(jì)2.1原始數(shù)據(jù)用戶輸入記錄的個(gè)數(shù)，數(shù)據(jù)由隨機(jī)數(shù)產(chǎn)生器生成。2.2輸出數(shù)據(jù)產(chǎn)生的隨機(jī)數(shù)分別用

4、起泡排序、直插排序、選擇排序、快速排序、歸并排序這些排序方法進(jìn)行排序，輸出關(guān)鍵字的比較次數(shù)和移動(dòng)次數(shù)。2.3數(shù)據(jù)處理主程序產(chǎn)生1組隨機(jī)數(shù)起泡排序直插排序快速排序堆排序選擇排序記錄關(guān)鍵字的比較次數(shù)和移動(dòng)次數(shù)將隨機(jī)數(shù)保存在數(shù)組中循環(huán)50次輸出關(guān)鍵字的比較次數(shù)、移動(dòng)次數(shù)的平均值3 算法描述3.1邏輯結(jié)構(gòu)及存儲(chǔ)結(jié)構(gòu)以順序表為存儲(chǔ)結(jié)構(gòu)typedef structkeytype key;datatype;3.2系統(tǒng)的模塊劃分及模塊功能mainselectsortbubblesortinsertsortquicksortheapsortoutput系統(tǒng)分為兩個(gè)模塊3.2.1主程序模塊void main()3

5、.2.2可排序表單元模塊冒泡排序：void bubblesort(datatype a,int n)插入排序：void insertsort(datatype a,int n)直接選擇排序：void selectsort(datatype a,int n)快速排序：void quicksort(datatype a,int low,int high)希爾排序：void shellsort(datatype a,int n,int d,int numofd)堆排序：void creatheap(datatype a,int n,int h)3.3程序代碼5頭文件：typedef int keyt

6、ype;typedef structkeytype key;datatype;static long int count1=0,count2=0;/*冒泡排序*/void bubblesort(datatype a,int n)int i,j,flag=1;datatype temp;for(i=1;in&flag=1;i+)flag=0;for(j=0;jaj+1.key)count2+;flag=1;temp=aj;count1+;aj=aj+1;count1+;aj+1=temp;count1+;/*插入排序*/void insertsort(datatype a,int n)int i

7、,j;datatype temp;for(i=0;i-1&temp.keyaj.key)count2+;aj+1=aj;count1+;j-;aj+1=temp;count1+;/*選擇排序*/void selectsort(datatype a,int n)int i,j,sm;datatype temp;for(i=0;in-1;i+)sm=i;/設(shè)第i個(gè)數(shù)據(jù)元素關(guān)鍵字最小for(j=i+1;jn;j+)/尋找關(guān)鍵字最小的數(shù)據(jù)元素if(aj.keyasm.key)sm=j;/記住最小元素的下標(biāo)count2+;if(sm!=i)/當(dāng)最小元素的下標(biāo)不為i時(shí)交換位置temp=ai;count1+

8、;ai=asm;count1+;asm=temp;count1+;/*快速排序*/void quicksort(datatype a,int low,int high)/用遞歸方法對(duì)數(shù)據(jù)元素進(jìn)行快速排序int i=low,j=high;datatype temp=alow;/取第一個(gè)元素為標(biāo)準(zhǔn)數(shù)據(jù)元素while(ij)while(ij&temp.key=aj.key)j-;/在數(shù)組的右端掃描count2+;if(ij)ai=aj;count1+;i+;while(ij&ai.keytemp.key)i+;/在數(shù)組的左端掃描count2+;if(ij)aj=ai;count1+;j-;ai=te

9、mp;count1+;if(lowi) quicksort(a,low,i-1);/對(duì)左端子集合進(jìn)行遞歸if(ihigh) quicksort(a,j+1,high);/對(duì)右端子集合進(jìn)行遞歸/*希爾排序*/void shellsort(datatype a,int n,int d,int numofd)/用希爾排序法對(duì)元素a0an-1排序，d0dm為希爾增量值int i,j,k,m,span;datatype temp;for(m=0;mnumofd;m+)span=dm;for(k=0;kspan;k+)/共span個(gè)小組for(i=k;i-1&temp.keyaj.key)count2+;

10、aj+span=aj;count1+;j=j-span;aj+span=temp;count1+;/*堆排序*/void creatheap(datatype a,int n,int h)int i,j,flag;datatype temp;i=h;/i為要建堆的二叉樹根結(jié)點(diǎn)下標(biāo)j=2*i+1;/ j為i的左孩子結(jié)點(diǎn)的下標(biāo)temp=ai;count1+;flag=0;/沿左右孩子中值較大者重復(fù)向下篩選while(jn&flag!=1)if(jn-1&aj.keyaj.key)flag=1;/標(biāo)記結(jié)束篩選條件count2+;否則把a(bǔ)j上移else/ai=aj;count1+;i=j;j=2*i+

11、1;ai=temp;count1+;void initcreatheap(datatype a,int n)int i;for(i=(n-1)/2;i=0;i-)creatheap(a,n,i);void heapsort(datatype a,int n)int i,count=0;datatype temp;initcreatheap(a,n);/初始化創(chuàng)建最大堆for(i=n-1;i0;i-)/當(dāng)前最大堆個(gè)數(shù)每次遞減1temp=a0;count1+;a0=ai;count1+;ai=temp;count1+;creatheap(a,i,0);/調(diào)整根結(jié)點(diǎn)滿足最大堆主程序：#include

12、#include#includesort.hvoid main()datatype r10000,r10000,a1000,b1000,c1000,e1000,f1000;int i,j,s; int p;int n; char yn; int d5=500,100,50,10,1; printf(請(qǐng)輸入產(chǎn)生隨機(jī)數(shù)個(gè)數(shù)n); scanf(%d,&p); n=p; while(1) int k=0; for(i=0;i(p/10);i+) srand(i+gettickcount(); for(j=0;j10;j+) rk.key=rand(); k+; printf(%8d,rk-1.key)

13、; printf(n*n);printf(1.測(cè)試冒泡排序n);printf(2.測(cè)試直接插入排序n);printf(3.測(cè)試選擇排序n);printf(4.測(cè)試快速排序n);printf(5.測(cè)試希爾排序n);printf(6.測(cè)試堆排序n);printf(*n);label_1:printf(請(qǐng)選擇); scanf(%d,&s);switch(s)case 1 : count1=0;count2=0;for(i=0;i10000;i+)ri.key=ri.key;bubblesort(r,n);printf(冒泡排序移動(dòng)次數(shù)%dn,count1);printf(冒泡排序比較次數(shù)%dn,co

14、unt2);break;case 2:count1=0;count2=0;for(i=0;i10000;i+)ai.key=ri.key;insertsort(a,n);printf(直接插入排序移動(dòng)次數(shù)%dn,count1);printf(直接插入排序比較次數(shù)%dn,count2);break; case 3:count1=0;count2=0;for(i=0;i10000;i+)bi.key=ri.key; selectsort(b,n);printf(選擇排序移動(dòng)次數(shù)%dn,count1);printf(選擇排序比較次數(shù)%dn,count2); break;case 4:count1=0

15、;count2=0;for(i=0;i10000;i+)ci.key=ri.key;quicksort(c,0,n-1);printf(快速排序移動(dòng)次數(shù)%dn,count1);printf(快速排序比較次數(shù)%dn,count2);break;case 5:count1=0;count2=0;for(i=0;i10000;i+)ei.key=ri.key; shellsort(e,n,d,5);printf(希爾排序移動(dòng)次數(shù)%dn,count1);printf(希爾排序比較次數(shù)%dn,count2);break;case 6:count1=0;count2=0;for(i=0;i10000;i+

16、)fi.key=ri.key;heapsort(f,n,0);printf(堆排序移動(dòng)次數(shù)%dn,count1);printf(堆排序比較次數(shù)%dn,count2);break;default:printf(選擇出錯(cuò)!n); getchar(); printf(是否繼續(xù)測(cè)試其他測(cè)試方法(y/n):n); scanf(%c,&yn); if(yn=y|yn=y) goto label_1; printf(是否換數(shù)據(jù)重新測(cè)試(y/n):n); getchar(); scanf(%c,&yn); if(yn!=y&yn!=y) break; 4 調(diào)試分析進(jìn)入調(diào)試界面后選擇要測(cè)試排序算法的序號(hào)，比如選

17、擇1，就對(duì)隨機(jī)產(chǎn)生的1000個(gè)數(shù)據(jù)用冒泡法進(jìn)行測(cè)試，結(jié)果是冒泡排序執(zhí)行次數(shù)726450，然后選擇是否繼續(xù)，若繼續(xù)選擇y，若退出測(cè)試選擇n。5 測(cè)試結(jié)果5.1測(cè)試用例及選擇原因記錄數(shù)分別輸入1000、10000、100000，之所以想用這三個(gè)記錄數(shù)測(cè)試，是想測(cè)試用選擇排序、起泡排序、直插排序、快速排序、歸并排序這五種排序方法，在記錄較小和較大時(shí)，關(guān)鍵字的比較次數(shù)和移動(dòng)次數(shù)，用以直觀的分析它們的性能。5.2 測(cè)試結(jié)果記錄數(shù)的個(gè)數(shù)關(guān)鍵字選擇排序起泡排序直插排序快速排序堆排序1000比較次數(shù)368194036移動(dòng)次數(shù)186812182310000比較次數(shù)4851980199624688移動(dòng)次數(shù)2817

18、3941564327409100000比較次數(shù)49850199800199984879984移動(dòng)次數(shù)2974749592175354476854335.3 結(jié)論關(guān)鍵字選擇排序起泡排序直插排序快速排序堆排序記錄數(shù)比較次數(shù)較少最多最少較少較少較小移動(dòng)次數(shù)較少最多較少較少較少比較次數(shù)較少最多最少較少較少較大移動(dòng)次數(shù)最少最多較多較少較少5.4 結(jié)果分析（1）選擇排序的比較次數(shù)較少且為定值，但由于它在排序過(guò)程中要先查詢、再安置，所以性能上不夠穩(wěn)定。（2）起泡排序的比較次數(shù)和移動(dòng)次數(shù)在這五種排序方式中最多，所以起泡排序的排序性能相對(duì)于其他排序要低好多。（3）直插排序的比較次數(shù)和移動(dòng)次數(shù)相比較于其他幾種排序次數(shù)要少，所以效率相比較而言較高，性能較高，且較穩(wěn)定。從整體上來(lái)講性能較其他幾種排序較高。（4）快速排序在這幾種排序當(dāng)中從比較次數(shù)較少的，移動(dòng)次數(shù)多于選擇排序但低于其他三種排序，且其過(guò)程是先定一個(gè)基準(zhǔn)，大小各放一邊，再分別對(duì)兩邊多次操作，達(dá)到整體有序，所以性能上來(lái)看是最快最好的，但是不夠穩(wěn)定。由此可見(jiàn)上述內(nèi)部排序方法，每一種方法都有各