數(shù)據(jù)結(jié)構(gòu)排序綜合

1、【精品文檔】如有侵權(quán)，請聯(lián)系網(wǎng)站刪除，僅供學(xué)習與交流數(shù)據(jù)結(jié)構(gòu)排序綜合.精品文檔.目 錄1.需求分析12.概要設(shè)計13.詳細設(shè)計24.測試分析19課程設(shè)計總結(jié)22參 考 文 獻24一、需求分析問題描述：此次的任務(wù)是利用隨機函數(shù)產(chǎn)生N個隨機整數(shù)，對這些數(shù)進行多種方法進行排序，分別是插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序）。并把排序后的結(jié)果保存在不同的文件中。然后統(tǒng)計每一種排序方法的性能（以上機運行程序所花費的時間為準進行對比），找出其中兩種較快的方法?；疽螅簲?shù)據(jù)輸入的形式和輸入值的范圍：設(shè)定的隨機數(shù)據(jù)的范圍是0到30000，產(chǎn)生30000個，類型均為整型。數(shù)據(jù)輸出的

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

3、種，所以用數(shù)組的存儲結(jié)構(gòu)能合理利用存儲空間。而且我們所學(xué)的排序算法是基于數(shù)組的儲存結(jié)構(gòu)實現(xiàn)的。3、 系統(tǒng)功能設(shè)計Head.h：用于聲明必要的頭文件，函數(shù)及結(jié)構(gòu)體Srand.c：用于產(chǎn)生隨機數(shù)Writefile.c：用于將排序結(jié)果存入文件Print.c：用于輸出文件中的排序結(jié)果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ù)進行堆排

4、序Mergesort.c：用于將產(chǎn)生的隨機數(shù)進行歸并排序4、 各個程序模塊之間的層次（調(diào)用）關(guān)系：三、詳細設(shè)計1、數(shù)據(jù)類型設(shè)計：typedef int KeyType; /定義關(guān)鍵字類型typedef char InfoType10;typedef struct /記錄類型KeyType key; /關(guān)鍵字項InfoType data; /其他數(shù)據(jù)項,類型為InfoType RecType;2、 詳細算法：頭文件：/*Head.h*/#include<stdio.h>#include <stdlib.h>#include <time.h>#define Ma

5、xSize 20000typedef int KeyType; /定義關(guān)鍵字類型typedef char InfoType10;typedef struct /記錄類型KeyType key; /關(guān)鍵字項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.冒泡排序 vo

6、id ShellSort(RecType R,int n);/3.希爾排序 void 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 RMaxS

7、ize,R1MaxSize+1;void Menu() int i;clock_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(&qu

8、ot; 8.歸并排序n");printf(" 9.打印各種排序方法排序后的序列n");printf(" 10.清空屏幕n");printf(" 11.結(jié)束程序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=

9、Ri.key;InsertSort(R1,n);break;case 3:for (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-sta

10、rt)/CLOCKS_PER_SEC;printf("快速排序已經(jīng)完成！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=R

11、i.key;MergeSort(R1,n);break;case 9:print(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 sta

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

13、ration);Writefile(R,n,1);/*Heapsort.c*/#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調(diào)整到雙親結(jié)點位置上i=j; /修改i和j值,以便繼續(xù)向下

14、篩選j=2*i; else break; /篩選結(jié)束Ri=temp; /被篩選結(jié)點的值放入最終位置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_S

15、EC;printf("堆排序已經(jīng)完成！n");printf("算法用時%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; /從右向左

16、在有序區(qū)R0.i-1中找Ri的插入位置while (j>=0 && tmp.key<Rj.key) Rj+1=Rj; /將關(guān)鍵字大于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&q

17、uot;void Merge(RecType R,int low,int mid,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;

18、j+;k+;while (i<=mid) /將第1段余下部分復(fù)制到R1R1k=Ri;i+;k+;while (j<=high) /將第2段余下部分復(fù)制到R1R1k=Rj;j+;k+;for (k=0,i=low; i<=high; k+,i+) /將R1復(fù)制回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-

19、1);if (i+length-1<n) /余下兩個子表,后者長度小于lengthMerge(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)(fin

20、ish-start)/CLOCKS_PER_SEC;printf("歸并排序已經(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;/用于從文件輸出保存結(jié)果i=0;printf("排序結(jié)果如下：n");printf("插入排序：n");fp=fopen("

21、Resultfile/InsertSort.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/ShellSort.dat","rb");while(fread(&R2i

22、.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/BubbleSort.dat","rb");while(fread(&R2i.key,sizeof(int),1,fp)=1)i+;fclose(fp);for(i=0; i<MaxSize; i+)pr

23、intf("%d ",R2i.key);printf("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("

24、;選擇排序：n");fp=fopen("Resultfile/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

25、");while(fread(&R2i.key,sizeof(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)

26、;for(i=0; i<MaxSize; i+)printf("%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ū)間內(nèi)至少存在兩個元素的情況tmp=Rs; /用區(qū)間的第1個記錄作為基準while (i!=j) /從區(qū)間兩端交替向中間掃描,直至i=j為止while (j>i &am

27、p;& Rj.key>=tmp.key) j-; /從右向左掃描,找第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 Sele

28、ctSort(RecType R,int n)int i,j,k,l;RecType 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記下目前找到的最小關(guān)鍵字所在的位置if (k!=i) /交換Ri和Rktemp=Ri;Ri=Rk;Rk=temp; finish=clock();duration=(double)(fin

29、ish-start)/CLOCKS_PER_SEC;printf("選擇排序已經(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

30、) for (i=gap; i<n; i+) /對所有相隔gap位置的所有元素組進行排序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",du

31、ration);Writefile(R,n,7);/*Srand.c*/#include"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&qu

32、ot;void Writefile(RecType R1,int n,int k) 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("提示：排序結(jié)果已保存至BubbleSort.datn"

33、);break;case 2:if(fp=fopen("Resultfile/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("提示：排序結(jié)果已保存至Heapsort.datn");break;case 3:if(fp=fopen("Resultfile/InsertSort.dat&qu

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

35、turn;for(i=0; i<n; i+) fwrite(&R1i.key,1,sizeof(int),fp);fclose(fp);printf("提示：排序結(jié)果已保存至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),f

36、p);fclose(fp);printf("提示：排序結(jié)果已保存至QuickSort.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("提示：排序結(jié)果已保存至SelectSort.datn")

37、;break;case 7:if(fp=fopen("Resultfile/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("提示：排序結(jié)果已保存至ShellSort.datn");break;4、 調(diào)試分析 圖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后從文件打印出來的排序結(jié)果 圖10 圖11 圖12 圖13圖14圖15圖16圖17 輸入整數(shù)11，退出程序課程設(shè)計總結(jié)1、 調(diào)試過程中遇到的問題是如何解決的，以及對設(shè)計與實現(xiàn)的回顧討論與分析。我一開始先按照書本的介紹，將7個排序算法寫好，然后再去設(shè)計主函數(shù)來調(diào)用這