1、數據結構課程設計班級 計算機科學與技術（2） 學號 20082308054 姓名 陳進勝 指導教師 李振宏 時間： 年 月 日 至 年 月 日成績 指導教師簽字 年 月 日 排序綜合摘要：利用隨機函數產生N個隨機整數（20000以上），對這些數進行多種方法進行排序。要求：1)至少采用三種方法實現上述問題求解（提示，可采用的方法有插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序）。并把排序后的結果保存在不同的文件中。2)統計每一種排序方法的性能（以上機運行程序所花費的時間為準進行對比），找出其中兩種較快的方法。3)如果采用4種或4種以上的方法者，可適當加分。1設計目的：利用隨機

2、函數產生N個隨機整數（20000以上），對這些數進行多種方法進行排序2設計內容（1）顯示隨機數：調用Dip()函數輸出數組a。數組a中保存有隨機產生的隨機數。（2）直接選擇排序：通過n-I次關鍵字間的比較，從n-i+1個記錄中選出關鍵字最小的記錄，并和第i個記錄交換之。（4）冒泡排序：如果有n個數，則要進行n-1趟比較。在第1趟比較中要進行n-1次兩兩比較，在第j趟比較中要進行n-j次兩兩比較。（5）希爾排序：先將整個待排記錄序列分割成為若干子序列分別進行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行一次直接插入排序。（6）直接插入排序：將一個記錄插入到已排序好的有序表中，從

3、而得到一個新的、記錄數增1的有序表。設整個排序有n個數，則進行n-1趟插入，即：先將序列中的第1個記錄看成是一個有序的子序列，然后從第2個記錄起逐個進行插入，直至整個序列變成按關鍵字非遞減有序列為止。各種函數的存儲都是通過順序存儲來存儲的3源程序system("cls");menu(); scanf("%d",&p); 包括加載頭文件，定義結構體、常量和變量，并對它們進行初始化工作。 #include <stdio.h> /*標準輸入輸出函數庫*/#include <conio.h> /*屏幕操作函數庫*/#include

4、 <stdlib.h> /*標準函數庫*/#include <time.h> /*時間函數庫*/#define N 20000void Disp(int a) /數組輸出函數int i;system("cls");for(i=0;i<N;i+)if(i-1)%10=9) printf("n"); printf("%-7d",ai); getchar();void InsertSort(int a) /插入排序 FILE *fp; fp=fopen("c:插入排序.txt","

5、w"); int i,j,temp; int bN; for(i=0;i<N;i+) bi=ai; for(i=1;i<N;i+) temp=bi; for(j=i;j>0&&bj-1>temp;j-) bj=bj-1; bj=temp; for(i=0;i<N;i+) fprintf(fp,"%d ",bi); fclose(fp); void SelectSort(int a) /選擇排序 FILE *fp; fp=fopen("c:選擇排序.txt","w"); int i

6、,j,k; int bN; for(i=0;i<N;i+) bi=ai; for(i=0;i<N-1;i+) k=i; for(j=i+1;j<N;j+) if(bj<bk) k=j; if(k!=i) int temp; temp=bk; bk=bi; bi=temp; for(i=0;i<N;i+) fprintf(fp,"%d ",bi);fclose(fp);void BubbleSort(int a)/*冒泡排序算法*/ FILE *fp; fp=fopen("c:冒泡排序.txt","w");

7、int i,j,temp; int bN; for(i=0;i<N;i+) bi=ai;for (i=0;i<N-1;i+) for (j=N-1;j>i;j-)/*比較,找出本趟最小關鍵字的記錄*/if (bj<bj-1) temp=bj; /*進行交換,將最小關鍵字記錄前移*/bj=bj-1;bj-1=temp; for(i=0;i<N;i+) fprintf(fp,"%d ",bi);fclose(fp); void ShellSort(int a)/*希爾排序算法*/FILE *fp; fp=fopen("c:希爾排序.txt

8、","w");int i,j,d,temp;int bN; for(i=0;i<N;i+) bi=ai;d=N/2;/*d取初值n/2*/while (d>0) for (i=d;i<N;i+)/*將bd.n-1分別插入各組當前有序區中*/j=i-d;while (j>=0 && bj>bj+d) temp=bj; /*bj與bj+d交換*/bj=bj+d;bj+d=temp;j=j-d; d=d/2; /*遞減增量d*/ for(i=0;i<N;i+) fprintf(fp,"%d ",bi

9、);fclose(fp);void menu() /主菜單顯示函數/ printf(" *綜合排序*n"); printf(" 08計算機二班 陳進勝 n"); printf(" * 菜 單 * n"); printf(" * n"); printf(" §1-顯示隨機數 § n"); printf(" §2-直接選擇排序 § n"); printf(" §3-冒泡排序 § n");printf(

10、" §4-希爾排序 § n"); printf(" §5-直接插入排序 § n"); printf(" §6-輸出最短兩個排序 § n"); printf(" §0-退出 § n"); printf(" *n"); printf("n=>請在上述序號中選擇一個并輸入:"); void Wrong() /錯誤提示函數printf("n=>按鍵錯誤!n");getcha

11、r();void PRT1(double time) /輸出運行時間函數system("cls");printf("=>程序運行時間為%f秒。",time);printf("n請輸入回車鍵返回!");getchar();getchar();double Min(double x,double y) /求最小值if(x>y)return y;else return x;void main() /主函數 int i,p,aN; double time1,time2,time3,time4,temp;double one,two

12、;clock_t start,end; srand(int)time(NULL); /*隨機種子*/ for(i=0;i<N;i+) ai=rand()%30000+1; while(1)if(p=0) printf("=>謝謝使用!n"); getchar(); break;switch(p)case 1:Disp(a);getchar();break; case 2: start=clock();SelectSort(a);end=clock();time1=(double)(end-start)/CLOCKS_PER_SEC; PRT1(time1);br

13、eak; case 3: start=clock();BubbleSort(a);end=clock();time2=(double)(end-start)/CLOCKS_PER_SEC; PRT1(time2); break;case 4: start=clock();ShellSort(a);end=clock();time3=(double)(end-start)/CLOCKS_PER_SEC; PRT1(time3); break; case 5: start=clock(); InsertSort(a); end=clock(); time4=(double)(end-start)/

14、CLOCKS_PER_SEC; PRT1(time4); break; case 6: one=Min(Min(time1,time2),Min(time3,time4); if(one=time1) two=Min(Min(time2,time3),time4); printf("=>時間最短的排序是“直接選擇排序”。n"); if(one=time2) two=Min(Min(time1,time3),time4); printf("=>時間最短的排序是“冒泡排序”。n"); if(one=time3) two=Min(Min(time1

15、,time2),time4); printf("=>時間最短的排序是“希爾排序”。n"); if(one=time4) two=Min(Min(time1,time2),time3); printf("=>時間最短的排序是“直接插入排序”。n"); if(two=time1) printf("=>其次的排序是“直接選擇排序”。n"); if(two=time2) printf("=>其次的排序是“冒泡排序”。n"); if(two=time3) printf("=>其次的排序

16、是“希爾排序”。n"); if(two=time4) printf("=>其次的排序是“直接插入排序”。n"); getchar();getchar();break;default:Wrong();getchar();break;流程圖調試分析系統運行圖這個我們開始進入的選擇菜單，我們只要選擇06這7個數字就可以操作了。（如圖1） （圖1）選擇1就會出現20000個隨機數，在這里不能全部顯示出來，只顯示了一部分。（圖2） （圖2） 選擇2就進行直接選擇排序，（如圖3）圖中只出現了直接排序的時間，排好序的數已經從到了c盤中的“選擇排序.txt”文件。分別選擇3、4、5就會分別進入了冒泡排序（圖4）、希爾排序（圖5）、直接插入排序（圖6）。顯示同選擇2。 （圖3）（圖4）（圖5）（圖6）選擇6則會出現最快和其次的排序方法，（