1、目 錄1.需求分析12.概要設計13.詳細設計24.測試分析19課程設計總結22參 考 文 獻24一、需求分析問題描述：此次的任務是利用隨機函數(shù)產(chǎn)生N個隨機整數(shù)，對這些數(shù)進行多種方法進行排序，分別是插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序）。并把排序后的結果保存在不同的文件中。然后統(tǒng)計每一種排序方法的性能（以上機運行程序所花費的時間為準進行對比），找出其中兩種較快的方法。基本要求：數(shù)據(jù)輸入的形式和輸入值的范圍：設定的隨機數(shù)據(jù)的范圍是0到30000，產(chǎn)生30000個，類型均為整型。數(shù)據(jù)輸出的形式：程序以一個排序完成后的有序數(shù)組來輸出。程序所設計的功能：（1）構建菜單，為

2、每種排序方法設定一個選項數(shù)字，用戶可根據(jù)需要選擇不同的排序方法。可以選擇的方法有：插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序共七種。（2） 每種排序結束后自動計算該排序的耗時。（3） 將排序后的數(shù)據(jù)保存到相應的文件里面。（4）數(shù)據(jù)由隨機函數(shù)產(chǎn)生。二、概要設計為了實現(xiàn)需求分析中的功能，可以從以下3個方面著手設計。1、 主界面設計利用switch函數(shù)設計出菜單，即通過case分別調用不同的排序方法。2、存儲結構設計本次存儲結構僅用到了數(shù)組的儲存結構。原因：需要存儲的數(shù)據(jù)是連續(xù)的，數(shù)據(jù)類型也只有一種，所以用數(shù)組的存儲結構能合理利用存儲空間。而且我們所學的排序算法是基于數(shù)組的儲

3、存結構實現(xiàn)的。3、 系統(tǒng)功能設計Head.h：用于聲明必要的頭文件，函數(shù)及結構體Srand.c：用于產(chǎn)生隨機數(shù)Writefile.c：用于將排序結果存入文件Print.c：用于輸出文件中的排序結果Insertsort.c：用于將產(chǎn)生的隨機數(shù)進行插入排序Shellsort.c：用于將產(chǎn)生的隨機數(shù)進行希爾排序Bubblesort.c：用于將產(chǎn)生的隨機數(shù)進行冒泡排序Quicksort.c：用于將產(chǎn)生的隨機數(shù)進行快速排序Selectsort.c：用于將產(chǎn)生的隨機數(shù)進行選擇排序Heapsort.c：用于將產(chǎn)生的隨機數(shù)進行堆排序Mergesort.c：用于將產(chǎn)生的隨機數(shù)進行歸并排序4、 各個程序模塊之間的

4、層次（調用）關系：三、詳細設計1、數(shù)據(jù)類型設計：typedef int KeyType; /定義關鍵字類型typedef char InfoType10;typedef struct /記錄類型KeyType key; /關鍵字項InfoType data; /其他數(shù)據(jù)項,類型為InfoType RecType;2、 詳細算法：頭文件：/*Head.h*/#include<stdio.h>#include <stdlib.h>#include <time.h>#define MaxSize 20000typedef int KeyType; /定義關鍵字類型

5、typedef char InfoType10;typedef struct /記錄類型KeyType key; /關鍵字項InfoType data; /其他數(shù)據(jù)項,類型為InfoType RecType;/排序的記錄類型定義void InsertSort(RecType R,int n);/1.插入排序 void Srand(RecType R);/隨機函數(shù) void print(RecType R,int a);/打印函數(shù) void BubbleSort(RecType R,int n);/2.冒泡排序 void ShellSort(RecType R,int n);/3.希爾排序 vo

6、id QuickSort(RecType R,int s,int t);/4.快速排序 void SelectSort(RecType R,int n);/5.選擇排序 void Heapsort(RecType R,int n);/6.堆排序 void MergeSort(RecType R,int n);/7.歸并排序 void Writefile(RecType R,int n,int k);/寫入文件 主程序：/*Main.c*/#include"Head.h"RecType RMaxSize,R1MaxSize+1;void Menu() int i;clock_

7、t start,finish;double duration;int a,n=MaxSize;printf(" 1.產(chǎn)生隨機數(shù)n");printf(" 2.插入排序n");printf(" 3.冒泡排序n");printf(" 4.希爾排序n");printf(" 5.快速排序n");printf(" 6.選擇排序n");printf(" 7.堆排序n");printf(" 8.歸并排序n");printf(" 9.打印各種排

8、序方法排序后的序列n");printf(" 10.清空屏幕n");printf(" 11.結束程序n");fflush(stdin);printf("請輸入一個整數(shù)：");scanf("%d",&a);printf("n");fflush(stdin);switch(a) case 1:Srand(R);break;case 2:for (i=0; i<MaxSize; i+)R1i.key=Ri.key;InsertSort(R1,n);break;case 3:for

9、 (i=0; i<MaxSize; i+)R1i.key=Ri.key;BubbleSort(R1,n);break;case 4:for (i=0; i<MaxSize; i+)R1i.key=Ri.key;ShellSort(R1,n);break;case 5:for (i=0; i<MaxSize; i+)R1i.key=Ri.key;start =clock();QuickSort(R1,0,n-1);finish=clock();duration=(double)(finish-start)/CLOCKS_PER_SEC;printf("快速排序已經(jīng)完成

10、！n");printf("算法用時%f秒nn",duration);Writefile(R1,n,5);break;case 6:for (i=0; i<MaxSize; i+)R1i.key=Ri.key;SelectSort(R1,n);break;case 7:for (i=0; i<MaxSize; i+)R1i+1.key=Ri.key;Heapsort(R1,n);break;case 8:for (i=0; i<MaxSize; i+)R1i.key=Ri.key;MergeSort(R1,n);break;case 9:print

11、(R,a);break;case 10:system("cls");break;case 11:exit(0);default:printf("輸入有誤！請重新輸入n");break;int main() while(1) Menu();return 0;子程序：/*Bubblesort.c*/#include"Head.h"void BubbleSort(RecType R,int n) int i,j,k;RecType tmp;clock_t start,finish;double duration;start =clock()

12、;for (i=0; i<n-1; i+) for (j=n-1; j>i; j-)/比較,找出本趟最小關鍵字的記錄if (Rj.key<Rj-1.key) tmp=Rj; /Rj與Rj-1進行交換,將最小關鍵字記錄前移Rj=Rj-1;Rj-1=tmp;finish=clock();duration=(double)(finish-start)/CLOCKS_PER_SEC;printf("冒泡排序已經(jīng)完成！n");printf("算法用時%f秒nn",duration);Writefile(R,n,1);/*Heapsort.c*/#

13、include"Head.h"void sift(RecType R,int low,int high) int i=low,j=2*i; /Rj是Ri的左孩子RecType temp=Ri;while (j<=high) if (j<high && Rj.key<Rj+1.key) /若右孩子較大,把j指向右孩子j+; /變?yōu)?i+1if (temp.key<Rj.key) Ri=Rj; /將Rj調整到雙親結點位置上i=j; /修改i和j值,以便繼續(xù)向下篩選j=2*i; else break; /篩選結束Ri=temp; /被篩選結

14、點的值放入最終位置void Heapsort(RecType R,int n) int i;RecType tmp;clock_t start,finish;double duration;start =clock();for(i=n/2; i>=1; i-)sift(R,i,n);for(i=n; i>=2; i-) tmp=R1;R1=Ri;Ri=tmp;sift(R,1,i-1);finish=clock();duration=(double)(finish-start)/CLOCKS_PER_SEC;printf("堆排序已經(jīng)完成！n");printf(

15、"算法用時%f秒nn",duration);Writefile(R,n,2);/*Insertsort.c*/#include"Head.h"void InsertSort(RecType R,int n) /對R0.n-1按遞增有序進行直接插入排序int i,j,k;RecType tmp;clock_t start,finish;double duration;start =clock();for (i=1; i<n; i+) tmp=Ri;j=i-1; /從右向左在有序區(qū)R0.i-1中找Ri的插入位置while (j>=0 &&

16、amp; tmp.key<Rj.key) Rj+1=Rj; /將關鍵字大于Ri.key的記錄后移j-;Rj+1=tmp; /在j+1處插入Rifinish=clock();duration=(double)(finish-start)/CLOCKS_PER_SEC;printf("插入排序已經(jīng)完成！n");printf("算法用時%f秒nn",duration);Writefile(R,n,3);/*Mergesort.c*/#include"Head.h"void Merge(RecType R,int low,int mid

17、,int high) RecType *R1;int i=low,j=mid+1,k=0; /k是R1的下標,i、j分別為第1、2段的下標R1=(RecType *)malloc(high-low+1)*sizeof(RecType); /動態(tài)分配空間while (i<=mid && j<=high) /在第1段和第2段均未掃描完時循環(huán)if (Ri.key<=Rj.key) /將第1段中的記錄放入R1中R1k=Ri;i+;k+; else /將第2段中的記錄放入R1中R1k=Rj;j+;k+;while (i<=mid) /將第1段余下部分復制到R1R1

18、k=Ri;i+;k+;while (j<=high) /將第2段余下部分復制到R1R1k=Rj;j+;k+;for (k=0,i=low; i<=high; k+,i+) /將R1復制回R中Ri=R1k;void MergePass(RecType R,int length,int n) /對整個數(shù)序進行一趟歸并int i;for (i=0; i+2*length-1<n; i=i+2*length) /歸并length長的兩相鄰子表Merge(R,i,i+length-1,i+2*length-1);if (i+length-1<n) /余下兩個子表,后者長度小于le

19、ngthMerge(R,i,i+length-1,n-1); /歸并這兩個子表void MergeSort(RecType R,int n) /自底向上的二路歸并算法int length;clock_t start,finish;double duration;start =clock();for (length=1; length<n; length=2*length) /進行l(wèi)og2n趟歸并MergePass(R,length,n);finish=clock();duration=(double)(finish-start)/CLOCKS_PER_SEC;printf("歸

20、并排序已經(jīng)完成！n");printf("算法用時%f秒nn",duration);Writefile(R,n,4);/*Print.c*/#include"Head.h"void print(RecType R,int a) FILE *fp;int i;RecType R2MaxSize+1;/用于從文件輸出保存結果i=0;printf("排序結果如下：n");printf("插入排序：n");fp=fopen("Resultfile/InsertSort.dat","rb

21、");while(fread(&R2i.key,sizeof(int),1,fp)=1)i+;fclose(fp);for(i=0; i<MaxSize; i+)printf("%d ",R2i.key);printf("n");i=0;printf("希爾排序：n");fp=fopen("Resultfile/ShellSort.dat","rb");while(fread(&R2i.key,sizeof(int),1,fp)=1)i+;fclose(fp);f

22、or(i=0; i<MaxSize; i+)printf("%d ",R2i.key);printf("n");i=0;printf("冒泡排序：n");fp=fopen("Resultfile/BubbleSort.dat","rb");while(fread(&R2i.key,sizeof(int),1,fp)=1)i+;fclose(fp);for(i=0; i<MaxSize; i+)printf("%d ",R2i.key);printf(&qu

23、ot;n");i=0;printf("快速排序：n");fp=fopen("Resultfile/QuickSort.dat","rb");while(fread(&R2i.key,sizeof(int),1,fp)=1)i+;fclose(fp);for(i=0; i<MaxSize; i+)printf("%d ",R2i.key);printf("n");i=0;printf("選擇排序：n");fp=fopen("Resultfile

24、/SelectSort.dat","rb");while(fread(&R2i.key,sizeof(int),1,fp)=1)i+;fclose(fp);for(i=0; i<MaxSize; i+)printf("%d ",R2i.key);printf("n");i=1;printf("堆排序：n");fp=fopen("Resultfile/Heapsort.dat","rb");while(fread(&R2i.key,sizeof(

25、int),1,fp)=1)i+;fclose(fp);for(i=1; i<MaxSize+1; i+)printf("%d ",R2i.key);printf("n");i=0;printf("歸并排序：n");fp=fopen("Resultfile/MergeSort.dat","rb");while(fread(&R2i.key,sizeof(int),1,fp)=1)i+;fclose(fp);for(i=0; i<MaxSize; i+)printf("

26、%d ",R2i.key);printf("n");/*Quicksort.c*/#include"Head.h"void QuickSort(RecType R,int s,int t) /對Rs至Rt的元素進行快速排序int i=s,j=t;RecType tmp;if (s<t) /區(qū)間內至少存在兩個元素的情況tmp=Rs; /用區(qū)間的第1個記錄作為基準while (i!=j) /從區(qū)間兩端交替向中間掃描,直至i=j為止while (j>i && Rj.key>=tmp.key) j-; /從右向左掃描,

27、找第1個小于tmp.key的RjRi=Rj;/找到這樣的Rj,Ri"Rj交換while (i<j && Ri.key<=tmp.key) i+;/從左向右掃描,找第1個大于tmp.key的記錄RiRj=Ri;/找到這樣的Ri,Ri"Rj交換Ri=tmp;QuickSort(R,s,i-1); /對左區(qū)間遞歸排序QuickSort(R,i+1,t); /對右區(qū)間遞歸排序/*Selectsort.c*/#include"Head.h"void SelectSort(RecType R,int n)int i,j,k,l;RecTy

28、pe temp;clock_t start,finish;double duration;start =clock();for (i=0;i<n-1;i+) /做第i趟排序k=i;for (j=i+1;j<n;j+) /在當前無序區(qū)Ri.n-1中選key最小的Rkif (Rj.key<Rk.key)k=j; /k記下目前找到的最小關鍵字所在的位置if (k!=i) /交換Ri和Rktemp=Ri;Ri=Rk;Rk=temp; finish=clock();duration=(double)(finish-start)/CLOCKS_PER_SEC;printf("選

29、擇排序已經(jīng)完成！n");printf("算法用時%f秒nn",duration);Writefile(R,n,6);/*Shellsort.c*/#include"Head.h"void ShellSort(RecType R,int n) /希爾排序算法int i,j,gap,k;RecType tmp;gap=n/2;/增量置初值clock_t start,finish;double duration;start =clock();while (gap>0) for (i=gap; i<n; i+) /對所有相隔gap位置的所有

30、元素組進行排序tmp=Ri;j=i-gap;while (j>=0 && tmp.key<Rj.key) /對相隔gap位置的元素組進行排序Rj+gap=Rj;j=j-gap;Rj+gap=tmp;j=j-gap;gap=gap/2;/減小增量finish=clock();duration=(double)(finish-start)/CLOCKS_PER_SEC;printf("希爾排序已經(jīng)完成！n");printf("算法用時%f秒nn",duration);Writefile(R,n,7);/*Srand.c*/#inc

31、lude"Head.h"void Srand(RecType R) int i;time_t t;srand(unsigned) time(&t);printf("隨機函數(shù)產(chǎn)生的隨機序列如下：n");for (i=0; i<MaxSize; i+)printf("%d ",Ri.key=(rand()%MaxSize);printf("nnn");/*Writefile.c*/#include"Head.h"void Writefile(RecType R1,int n,int k

32、) int i;FILE *fp;switch(k) case 1:if(fp=fopen("Resultfile/BubbleSort.dat","wb")=NULL) printf("t提示：不能創(chuàng)建文件n");return;for(i=0; i<n; i+) fwrite(&R1i.key,1,sizeof(int),fp);fclose(fp);printf("提示：排序結果已保存至BubbleSort.datn");break;case 2:if(fp=fopen("Resultf

33、ile/Heapsort.dat","wb")=NULL) printf("t提示：不能創(chuàng)建文件n");return;for(i=1; i<n+1; i+) fwrite(&R1i.key,1,sizeof(int),fp);fclose(fp);printf("提示：排序結果已保存至Heapsort.datn");break;case 3:if(fp=fopen("Resultfile/InsertSort.dat","wb")=NULL) printf("t

34、提示：不能創(chuàng)建文件n");return;for(i=0; i<n; i+) fwrite(&R1i.key,1,sizeof(int),fp);fclose(fp);printf("提示：排序結果已保存至InsertSort.datn");break;case 4:if(fp=fopen("Resultfile/MergeSort.dat","wb")=NULL) printf("t提示：不能創(chuàng)建文件n");return;for(i=0; i<n; i+) fwrite(&R1

35、i.key,1,sizeof(int),fp);fclose(fp);printf("提示：排序結果已保存至MergeSort.datn");break;case 5:if(fp=fopen("Resultfile/QuickSort.dat","wb")=NULL) printf("t提示：不能創(chuàng)建文件n");return;for(i=0; i<n; i+) fwrite(&R1i.key,1,sizeof(int),fp);fclose(fp);printf("提示：排序結果已保存至Qu

36、ickSort.datn");break;case 6:if(fp=fopen("Resultfile/SelectSort.dat","wb")=NULL) printf("t提示：不能創(chuàng)建文件n");return;for(i=0; i<n; i+) fwrite(&R1i.key,1,sizeof(int),fp);fclose(fp);printf("提示：排序結果已保存至SelectSort.datn");break;case 7:if(fp=fopen("Resultfi

37、le/ShellSort.dat","wb")=NULL) printf("t提示：不能創(chuàng)建文件n");return;for(i=0; i<n; i+) fwrite(&R1i.key,1,sizeof(int),fp);fclose(fp);printf("提示：排序結果已保存至ShellSort.datn");break;4、 調試分析 圖1 菜單界面 圖2 輸入整數(shù)1，產(chǎn)生20000個隨機數(shù) 圖3 輸入2，插入排序 圖4 輸入3，冒泡排序 圖5 輸入4，希爾排序 圖6 輸入5，快速排序 圖7 輸入6，選擇排序 圖8 輸入7，堆排序圖9 輸入8，歸并排序圖10至圖16為輸入9后從文件打印出來的排序結果 圖10 圖11 圖12 圖13圖14圖15圖16圖17 輸入整數(shù)11，退出程序課程設計總結1、 調試過程中遇到的問題是如何解決的，以及對設計與實現(xiàn)的回顧討論與分析。我一開始先按照書本的介紹，將7個排序算法寫好，然后再去設計主函數(shù)來調用這些排序算法。在