隨機(jī)函數(shù)產(chǎn)生進(jìn)行多種方法排序排序

1、精選優(yōu)質(zhì)文檔-傾情為你奉上 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告專(zhuān) 業(yè) 信息管理與信息系統(tǒng) 班 級(jí) 姓 名 趙文龍 學(xué) 號(hào) 時(shí) 間 2013.12.12 課程設(shè)計(jì)：排序綜合一、任務(wù)描述（1）至少采用三種方法實(shí)現(xiàn)上述問(wèn)題求解（提示，可采用的方法有插入排序、希爾排序、冒泡排序、快速排序、選擇排序、堆排序、歸并排序）。并把排序后的結(jié)果保存在不同的文件中。2) 統(tǒng)計(jì)每一種排序方法的性能（以上機(jī)運(yùn)行程序所花費(fèi)的時(shí)間為準(zhǔn)進(jìn)行對(duì)比），找出其中兩種較快的方法。如果采用 4 種或 4 種以上的方法者，可適當(dāng)加分。二、問(wèn)題分析1、功能分析 分析設(shè)計(jì)課題的要求，要求編程實(shí)現(xiàn)以下功能：（1）顯示隨機(jī)數(shù)：調(diào)用Dip()函數(shù)輸出數(shù)組a。

2、數(shù)組a中保存有隨機(jī)產(chǎn)生的隨機(jī)數(shù)。 （2）直接選擇排序：通過(guò)n-I次關(guān)鍵字間的比較，從n-i+1個(gè)記錄中選出關(guān)鍵字最小的記錄，并和第i個(gè)記錄交換之。 （3）冒泡排序：如果有n個(gè)數(shù)，則要進(jìn)行n-1趟比較。在第1趟比較中要進(jìn)行n-1次兩兩比較，在第j趟比較中要進(jìn)行n-j次兩兩比較。 （4）希爾排序：先將整個(gè)待排記錄序列分割成為若干子序列分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄“基本有序”時(shí)，再對(duì)全體記錄進(jìn)行一次直接插入排序。 （5）直接插入排序：將一個(gè)記錄插入到已排序好的有序表中，從而得到一個(gè)新的、記錄數(shù)增1的有序表。設(shè)整個(gè)排序有n個(gè)數(shù)，則進(jìn)行n-1趟插入，即：先將序列中的第1個(gè)記錄看成是一個(gè)有序的

3、子序列，然后從第2個(gè)記錄起逐個(gè)進(jìn)行插入，直至整個(gè)序列變成按關(guān)鍵字非遞減有序列為止。（6）顯示各排序算法排序后的的數(shù)據(jù)和時(shí)間效率，并比較找出其中2種較快的方法。2、數(shù)據(jù)對(duì)象分析 排序方式：直接選擇排序、冒泡排序、希爾排序、直接插入排序顯示排序后的的數(shù)據(jù)和時(shí)間效率。三、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)1.主要全程變量及數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)： typedef struct KeyType key; InfoType otherinfo; RedType;typedef struct RedType rMAXSIZE+1; int length; SqList; 2.算法的入口參數(shù)及說(shuō)明#include <stdio

4、.h>#define MAXSIZE 20#define LT(a,b) (a)<(b) /宏定義typedef int KeyType; /定義關(guān)鍵字KeyType為inttypedef int InfoType; /定義關(guān)鍵字InfoType為inttypedef struct /RedType結(jié)構(gòu)定義 KeyType key; InfoType otherinfo; /記錄中其他信息域的類(lèi)型RedType;typedef struct /SqList結(jié)構(gòu)定義 RedType rMAXSIZE+1; /定義大小 int length; /length為待排記錄個(gè)數(shù)SqList;

5、四、功能設(shè)計(jì)（一）主控菜單設(shè)計(jì)為實(shí)現(xiàn)排序的操作功能，首先設(shè)計(jì)一個(gè)含有多個(gè)菜單項(xiàng)的主控菜單程序，然后再為這些菜單項(xiàng)配上相應(yīng)的功能。程序運(yùn)行后，給出11個(gè)菜單項(xiàng)的內(nèi)容和輸入提示，如下：歡迎來(lái)到排序綜合系統(tǒng)！菜單(1)-直接插入排序(2)-直接選擇排序(3)-冒泡排序(4)-快速排序(5)-堆排序 (6)-時(shí)間效率比較(7)-顯示隨機(jī)數(shù) (0)-退出系統(tǒng)請(qǐng)?jiān)谏鲜鲂蛱?hào)中選擇一個(gè)并輸入：（二）程序模塊結(jié)構(gòu)由課題要求可將程序劃分為以下幾個(gè)模塊（即實(shí)現(xiàn)程序功能所需的函數(shù)）：l 主控菜單項(xiàng)選擇函數(shù)menu_select()l 插入排序函數(shù)：InsertSort()l 選擇排序函數(shù)：SelectSort()l

6、冒泡排序函數(shù)：BubbleSort()l 堆排序函數(shù)：heapsort()（三）函數(shù)調(diào)用關(guān)系程序的主要結(jié)構(gòu)（函數(shù)調(diào)用關(guān)系）如下圖所示。 其中main()是主函數(shù)，它進(jìn)行菜單驅(qū)動(dòng)，根據(jù)選擇項(xiàng)10調(diào)用相應(yīng)的函數(shù)。（四）函數(shù)實(shí)現(xiàn)#include <stdio.h>#include <conio.h> #include <stdlib.h>#include <windows.h>#include <time.h>#define N 30000void Wrong() printf("n=>按鍵錯(cuò)誤!n");getch

7、ar();void Disp(int a)int i;system("cls"); for(i=0;i<N;i+) if(i-1)%10=9) printf("n"); printf("%-7d",ai); void InsertSort(int a,int p) /插入排序 int i,j,temp; for(i=1;i<N;i+) temp=ai; for(j=i;j>0&&aj-1>temp;j-) aj=aj-1; aj=temp; void SelectSort(int a,int p

8、) /選擇排序 int i,j,k; for(i=0;i<N-1;i+) k=i; for(j=i+1;j<N;j+) if(aj<ak) k=j; if(k!=i) int temp; temp=ak; ak=ai; ai=temp; void BubbleSort(int a,int p) /*冒泡排序算法*/ int i,j,temp; for (i=0;i<N-1;i+) for (j=N-1;j>i;j-) /*比較,找出本趟最小關(guān)鍵字的記錄*/ if (aj<aj-1) temp=aj; /*進(jìn)行交換,將最小關(guān)鍵字記錄前移*/ aj=aj-1;

9、aj-1=temp; void creatheap(int a,int i,int n) /創(chuàng)建堆int j;int t;t=ai;j=2*(i+1)-1;while(j<=n)if(j<n)&&(aj<aj+1)j+;if(t<aj)ai=aj;i=j;j=2*(i+1)-1;elsej=n+1;ai=t;void heapsort(int a,int n,int p) /堆排序int i;int t;for(i=n/2-1;i>=0;i-)creatheap(a,i,n-1);for(i=n-1;i>=1;i-)t=a0;a0=ai;ai

10、=t;creatheap(a,0,i-1);void quicksort(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(low<high) temp=alow; while(i!=j) while(i<j&&aj>temp)j-; if(i&

11、lt;j)ai=aj;i+; while(i<j&&ai<temp)i+; if(i<j)aj=ai;j-; ai=temp; top+;sttop.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;i<N;i+) bi=ai;LARGE_INTEGER m_liPerfFreq=0;QueryPerformanceFrequency(&m_liPerfFreq); LAR

12、GE_INTEGER m_liPerfStart=0; QueryPerformanceCounter(&m_liPerfStart);InsertSort(b,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秒；&q

13、uot;,time);FILE *fp; fp=fopen("直接插入排序.txt","w"); for(i=0;i<N;i+) fprintf(fp,"%d ",bi); fclose(fp);return(time);double TSelectSort(int a,int p)int i;int bN;for(i=0;i<N;i+)bi=ai;LARGE_INTEGER m_liPerfFreq=0;QueryPerformanceFrequency(&m_liPerfFreq); LARGE_INTEGER

14、 m_liPerfStart=0; QueryPerformanceCounter(&m_liPerfStart);SelectSort(b,p);if(p!=6)Disp(b);getchar();LARGE_INTEGER liPerfNow=0; QueryPerformanceCounter(&liPerfNow); double time=liPerfNow.QuadPart - m_liPerfStart.QuadPart; time/=m_liPerfFreq.QuadPart;printf("n用直接選擇排序法用的時(shí)間為%f秒；",time)

15、;FILE *fp; fp=fopen("直接選擇排序.txt","w");for(i=0;i<N;i+) fprintf(fp,"%d ",bi);fclose(fp);return(time);double TBubbleSort(int a,int p)int i;int bN;for(i=0;i<N;i+)bi=ai;LARGE_INTEGER m_liPerfFreq=0;QueryPerformanceFrequency(&m_liPerfFreq); LARGE_INTEGER m_liPerfSta

16、rt=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);getchar();printf("n用冒泡排序法用的時(shí)間為%f秒；",time);FILE *fp; fp=

17、fopen("冒泡排序.txt","w"); for(i=0;i<N;i+) fprintf(fp,"%d ",bi);fclose(fp);return(time);double Theapsort(int a,int n,int p) int i;int bN;for(i=0;i<N;i+)bi=ai;LARGE_INTEGER m_liPerfFreq=0;QueryPerformanceFrequency(&m_liPerfFreq); LARGE_INTEGER m_liPerfStart=0; Quer

18、yPerformanceCounter(&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("

19、;堆排序.txt","w");for(i=0;i<N;i+) fprintf(fp,"%d ",bi);fclose(fp);return(time);double Tquicksort(int a,int n,int p)int i;int bN; for(i=0;i<N;i+) bi=ai;LARGE_INTEGER m_liPerfFreq=0;QueryPerformanceFrequency(&m_liPerfFreq); LARGE_INTEGER m_liPerfStart=0; QueryPerformanc

20、eCounter(&m_liPerfStart);quicksort(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("快速排序.tx

21、t","w"); for(i=0;i<N;i+) fprintf(fp,"%d ",bi); fclose(fp); return(time);void BubleSort(double a) /時(shí)間數(shù)組的冒泡排序 int i,j; double temp; for(i=1;i<6;i+) for(j=4;j>=i;j-) if(aj+1<aj) temp=aj+1; aj+1=aj; aj=temp; void menu()printf(" 歡迎來(lái)到排序綜合系統(tǒng)! n");printf("

22、 = n");printf(" n");printf(" 菜 單 n");printf(" n");printf(" n");printf(" (1)-直接插入排序 n");printf(" (2)-直接選擇排序 n");printf(" (3)-冒泡排序 n");printf(" (4)-快速排序 n");printf(" (5)-堆排序 n");printf(" (6)-時(shí)間效率比較 n&qu

23、ot;);printf(" (7)-顯示隨機(jī)數(shù) n");printf(" (0)-退出系統(tǒng) n");printf("n 請(qǐng)?jiān)谏鲜鲂蛱?hào)中選擇一個(gè)并輸入: ");void main() int i,p,aN; srand(int)time(NULL); /*隨機(jī)種子*/ for(i=0;i<N;i+) ai=rand()%50000+1; while(1) system("cls"); menu(); scanf("%d",&p); if(p=0) printf("=>

24、謝謝使用!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)按任意鍵繼續(xù).");getchar();break; case 3:TBubbleSort(a,p);printf("n請(qǐng)按任意鍵繼續(xù).");getchar();break; case 4:Tquicksor

25、t(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=TBubbleSort(a,p);TIMES14=TIMES4=Tquicksort(a,N,p);TIMES15=TIME

26、S5=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(TIMES

27、1=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); if(TIMES2=TIMES14) printf("快速排序%f秒!n",TIMES2); if(TIMES2=TIMES15) printf("堆排序%f秒!n",TIMES