綜合排序數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

1、題 目：綜合排序-數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 院 系：信息工程學(xué)院專(zhuān) 業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)班 級(jí)：姓 名：學(xué) 號(hào)：指導(dǎo)老師:時(shí) 間：目錄一、問(wèn)題描述4二、內(nèi)容簡(jiǎn)介42.1 基本要求：42.2. 算法思想：42.3. 模塊劃分：42.4. 數(shù)據(jù)結(jié)構(gòu)：52.5. 源程序：52.6. 測(cè)試情況：14三、小結(jié)17一、 問(wèn)題描述利用隨機(jī)函數(shù)產(chǎn)生n個(gè)隨機(jī)整數(shù)（20000以上），對(duì)這些數(shù)進(jìn)行多種方法進(jìn)行排序。要求：1) 至少采用三種方法實(shí)現(xiàn)上述問(wèn)題求解（提示，可采用的方法有插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序）。并把排序后的結(jié)果保存在不同的文件中。2) 統(tǒng)計(jì)每一種排序方法的性能（以上機(jī)運(yùn)

2、行程序所花費(fèi)的時(shí)間為準(zhǔn)進(jìn)行對(duì)比），找出其中兩種較快的方法。3) 如果采用4種或4種以上的方法者，可適當(dāng)加分。二、 內(nèi)容簡(jiǎn)介2.1 基本要求：（1） 設(shè)計(jì)一個(gè)的菜單將在實(shí)現(xiàn)的功能顯示出來(lái)，并有選擇提示（2） 分別實(shí)現(xiàn)直接插入排序、折半插入排序、希爾排序、冒泡排序、快速排序、簡(jiǎn)單排序、堆排序算法；（3） 通過(guò)多種測(cè)試數(shù)據(jù)，對(duì)各種排序算法的時(shí)間復(fù)雜度和空間復(fù)雜度進(jìn)行比較2.2. 算法思想：1.處理流程圖開(kāi)始直接插入排序時(shí)間效率比較直接選擇排序顯示菜單冒泡排序快速排序堆排序顯示隨機(jī)數(shù)顯示排序后的的數(shù)據(jù)和時(shí)間效率輸入序號(hào)結(jié)束退出隨機(jī)數(shù)顯示各個(gè)排序法對(duì)同一組數(shù)據(jù)排序所用的時(shí)間和其中兩種較快的方法12345

3、670void bublesort(double a)時(shí)間數(shù)組的冒泡排序void insertsort(int a,int p)void selectsort(int a,int p)void disp(int a)void creatheap(int a,int i,int n) void heapsort(int a,int n,int p)double tinsertsort(int a,int p)void quicksort(int a,int n, int p)void bubblesort(int a,int p)double tselectsort(int a,int p)do

4、uble tquicksort(int a,int left, int right,int p)double tbubblesort(int a,int p)double theapsort(int a,int n,int p)3.設(shè)計(jì)一個(gè)高精度時(shí)間函數(shù)，分別測(cè)試各種排序的時(shí)間消耗；4.在主函數(shù)中，用開(kāi)關(guān)語(yǔ)句swtich()case 值1;break;case值n;break;default語(yǔ)句序列:n+1;調(diào)用各種排序算法，各種排序的時(shí)間消耗函數(shù)，從而在屏幕上輸出供選擇的菜單，各種排序時(shí)間和空間復(fù)雜度的比較。2.3. 模塊劃分：1.輸入初始數(shù)據(jù)函數(shù)：int makelist(recnode

5、*r) 2.輸出未排序前的數(shù)據(jù)函數(shù)：void undealoutlist(recnode *r,int n) 3.處理后的序列函數(shù)：void dealoutlist(recnode*r,int n) 4.這種排序的算法：void insertsort(recnode*r,int n)/直接插入排序void biinsertionsort (recnode*r, int n) / 折半插入排序void bublesort(recnode *r,int n) /冒泡排序int partition(recnode*r,int*low,int*high)/一趟快速排序void quicksort(re

6、cnode*r,int start,int end)/快速排序void selesort(recnode*r,int n)/直接選擇排序void shellsort(recnode *r,int n)/希爾排序void sift(recnode*r,int i,int m)void heapsort(recnode*r,int n)/堆排序5.排序時(shí)間測(cè)試函數(shù)：double tinsertsort(int len,recnode *a,int p)2.4. 數(shù)據(jù)結(jié)構(gòu)：1.預(yù)定義常量和自定義類(lèi)型：#define maxsize 100 typedef struct int key; recnod

7、e;2.基本函數(shù)的算法用以下形式表示：函數(shù)類(lèi)型 函數(shù)名（函數(shù)參數(shù)表）/算法說(shuō)明 語(yǔ)句序列/函數(shù)名。3.定義 int b,t,i,j; /b為記錄交換的次數(shù)，t為記錄排序的趟數(shù),i為排序的數(shù)據(jù)，j為暫存數(shù)據(jù)的臨時(shí)變量。4. 輸入初始數(shù)據(jù)函數(shù)中定義int k, j，k為輸入數(shù)據(jù)個(gè)數(shù)，j為輸入的數(shù)據(jù)。5.快速排序中定義static int w=0,int *low，*high。6.在直接選擇排序中定義int z，臨時(shí)儲(chǔ)存i的值。7.在希爾排序中定義int dk，記錄前后位置的增量。8.在排序時(shí)間消耗測(cè)試的函數(shù)和主函數(shù)中定義了int p，為菜單的序號(hào)。9.在主函數(shù)中定義int len，為測(cè)試數(shù)據(jù)的總長(zhǎng)

8、度。2.5. 源程序：插入排序核心代碼void insertsort(int a,int p) int i,j,temp; for(i=1;i0&aj-1temp;j-) aj=aj-1; aj=temp; 選擇排序核心代碼void selectsort(int a,int p) int i,j,k; for(i=0;in-1;i+) k=i; for(j=i+1;jn;j+) if(ajak) k=j; if(k!=i) int temp; temp=ak; ak=ai; ai=temp; 冒泡排序算法核心代碼void bubblesort(int a,int p) int i,j,temp

9、; for (i=0;ii;j-) /*比較,找出本趟最小關(guān)鍵字的記錄*/ if (ajaj-1) temp=aj; /*進(jìn)行交換,將最小關(guān)鍵字記錄前移*/ aj=aj-1; aj-1=temp; 創(chuàng)建堆核心代碼void creatheap(int a,int i,int n) int j;int t;t=ai;j=2*(i+1)-1;while(j=n)if(jn)&(ajaj+1)j+;if(t=0;i-)creatheap(a,i,n-1);for(i=n-1;i=1;i-)t=a0;a0=ai;ai=t;creatheap(a,0,i-1);快速排序核心代碼void quicksort

10、(int a,int n,int p) int i,j,low,high,temp,top=-1; struct node int low,high; stn; top+; sttop.low=0;sttop.high=n-1; while(top-1) low=sttop.low;high=sttop.high; top-; i=low;j=high; if(lowhigh) temp=alow; while(i!=j) while(itemp)j-; if(ij)ai=aj;i+; while(ij&aitemp)i+; if(ij)aj=ai;j-; ai=temp; top+;stto

11、p.low=low;sttop.high=i-1; top+;sttop.low=i+1;sttop.high=high; 時(shí)間部分代碼double tinsertsort(int a,int p)int i;int bn; for(i=0;in;i+) bi=ai;large_integer m_liperffreq=0;queryperformancefrequency(&m_liperffreq); large_integer m_liperfstart=0; queryperformancecounter(&m_liperfstart);insertsort(b,p);large_in

12、teger liperfnow=0; queryperformancecounter(&liperfnow); double time=liperfnow.quadpart - m_liperfstart.quadpart; time/=m_liperffreq.quadpart;if(p!=6)disp(b);getchar();printf(n用直接插入排序法用的時(shí)間為%f秒；,time);file *fp; fp=fopen(直接插入排序.txt,w); for(i=0;in;i+) fprintf(fp,%d ,bi); fclose(fp);return(time);double t

13、selectsort(int a,int p)int i;int bn;for(i=0;in;i+)bi=ai;large_integer m_liperffreq=0;queryperformancefrequency(&m_liperffreq); large_integer m_liperfstart=0; queryperformancecounter(&m_liperfstart);selectsort(b,p);if(p!=6)disp(b);getchar();large_integer liperfnow=0; queryperformancecounter(&liperfno

14、w); double time=liperfnow.quadpart - m_liperfstart.quadpart; time/=m_liperffreq.quadpart;printf(n用直接選擇排序法用的時(shí)間為%f秒；,time);file *fp; fp=fopen(直接選擇排序.txt,w);for(i=0;in;i+) fprintf(fp,%d ,bi);fclose(fp);return(time);double tbubblesort(int a,int p)int i;int bn;for(i=0;in;i+)bi=ai;large_integer m_liperffr

15、eq=0;queryperformancefrequency(&m_liperffreq); large_integer m_liperfstart=0; queryperformancecounter(&m_liperfstart);bubblesort(b,p);large_integer liperfnow=0; queryperformancecounter(&liperfnow); double time=liperfnow.quadpart - m_liperfstart.quadpart; time/=m_liperffreq.quadpart;if(p!=6)disp(b);g

16、etchar();printf(n用冒泡排序法用的時(shí)間為%f秒；,time);file *fp; fp=fopen(冒泡排序.txt,w); for(i=0;in;i+) fprintf(fp,%d ,bi);fclose(fp);return(time);double theapsort(int a,int n,int p) int i;int bn;for(i=0;in;i+)bi=ai;large_integer m_liperffreq=0;queryperformancefrequency(&m_liperffreq); large_integer m_liperfstart=0;

17、queryperformancecounter(&m_liperfstart);heapsort(b,n,p);large_integer liperfnow=0; queryperformancecounter(&liperfnow); double time=liperfnow.quadpart - m_liperfstart.quadpart; time/=m_liperffreq.quadpart;if(p!=6)disp(b);getchar();printf(n用堆排序法用的時(shí)間為%f秒；,time);file *fp; fp=fopen(堆排序.txt,w);for(i=0;in

18、;i+) fprintf(fp,%d ,bi);fclose(fp);return(time);double tquicksort(int a,int n,int p)int i;int bn; for(i=0;in;i+) bi=ai;large_integer m_liperffreq=0;queryperformancefrequency(&m_liperffreq); large_integer m_liperfstart=0; queryperformancecounter(&m_liperfstart);quicksort(b,n,p);large_integer liperfno

19、w=0; queryperformancecounter(&liperfnow); double time=liperfnow.quadpart - m_liperfstart.quadpart; time/=m_liperffreq.quadpart;if(p!=6) disp(b);getchar(); printf(n用快速排序法用的時(shí)間為%f秒；,time);file *fp;fp=fopen(快速排序.txt,w); for(i=0;in;i+) fprintf(fp,%d ,bi); fclose(fp); return(time);時(shí)間數(shù)組的冒泡排序void bublesort(

20、double a) int i,j; double temp; for(i=1;i=i;j-) if(aj+1請(qǐng)?jiān)谏鲜鲂蛱?hào)中選擇一個(gè)并輸入:);主函數(shù)代碼void main() int i,p,an; srand(int)time(null); /*隨機(jī)種子*/ for(i=0;i謝謝使用!n); getchar(); break; double times5,times15;/時(shí)間數(shù)組 switch(p) case 1:tinsertsort(a,p);printf(n請(qǐng)按任意鍵繼續(xù).);getchar();break; case 2:tselectsort(a,p);printf(n請(qǐng)按任

21、意鍵繼續(xù).);getchar();break; case 3:tbubblesort(a,p);printf(n請(qǐng)按任意鍵繼續(xù).);getchar();break; case 4:tquicksort(a,n,p);printf(n請(qǐng)按任意鍵繼續(xù).);getchar();break; case 5:theapsort(a,n,p);printf(n請(qǐng)按任意鍵繼續(xù).);getchar();break; case 6:system(cls);times11=times1=tinsertsort(a,p);times12=times2=tselectsort(a,p); times13=times3

22、=tbubblesort(a,p);times14=times4=tquicksort(a,n,p);times15=times5=theapsort(a,n,p);getchar(); bublesort(times); printf(nn); printf(排序這組數(shù)據(jù)兩種較快的排序法分別是：n); if(times1=times11) printf(直接插入排序:%f秒!n,times1); if(times1=times12) printf(直接選擇排序:%f秒!n,times1); if(times1=times13) printf(冒泡排序:%f秒!n,times1); if(times1=times14) printf(快速排序:%f秒!n,times1); if(times1=times15) printf(堆排序:%f秒!n,times1); if(times1!=times2) if(times2=times11) printf(直接插入排序:%f秒!n,times2); if(times2=times12) printf(直接選擇排序%f秒!n,times2); if(times2=times13) printf(冒泡排序%f秒!n,times2);