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

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

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

3、670void bublesort(double a)時間數(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è)計一個高精度時間函數(shù)，分別測試各種排序的時間消耗；4.在主函數(shù)中，用開關(guān)語句swtich()case 值1;break;case值n;break;default語句序列:n+1;調(diào)用各種排序算法，各種排序的時間消耗函數(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ù)：double tinsertsort(int len,recnode *a,int p)2.4. 數(shù)據(jù)結(jié)構(gòu)：1.預(yù)定義常量和自定義類型：#define maxsize 100 typedef struct int key; recnod

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

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; /*進行交換,將最小關(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; 時間部分代碼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用直接插入排序法用的時間為%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用直接選擇排序法用的時間為%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用冒泡排序法用的時間為%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用堆排序法用的時間為%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用快速排序法用的時間為%f秒；,time);file *fp;fp=fopen(快速排序.txt,w); for(i=0;in;i+) fprintf(fp,%d ,bi); fclose(fp); return(time);時間數(shù)組的冒泡排序void bublesort(

20、double a) int i,j; double temp; for(i=1;i=i;j-) if(aj+1請在上述序號中選擇一個并輸入:);主函數(shù)代碼void main() int i,p,an; srand(int)time(null); /*隨機種子*/ for(i=0;i謝謝使用!n); getchar(); break; double times5,times15;/時間數(shù)組 switch(p) case 1:tinsertsort(a,p);printf(n請按任意鍵繼續(xù).);getchar();break; case 2:tselectsort(a,p);printf(n請按任

21、意鍵繼續(xù).);getchar();break; case 3:tbubblesort(a,p);printf(n請按任意鍵繼續(xù).);getchar();break; case 4:tquicksort(a,n,p);printf(n請按任意鍵繼續(xù).);getchar();break; case 5:theapsort(a,n,p);printf(n請按任意鍵繼續(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);