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

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

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

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

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

5、typedef char InfoType10;typedef struct /記錄類(lèi)型KeyType key; /關(guān)鍵字項(xiàng)InfoType data; /其他數(shù)據(jù)項(xiàng),類(lèi)型為InfoType RecType;/排序的記錄類(lèi)型定義void InsertSort(RecType R,int n);/1.插入排序 void Srand(RecType R);/隨機(jī)函數(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);/寫(xiě)入文件 主程序：/*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)生隨機(jī)數(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.結(jié)束程序n");fflush(stdin);printf("請(qǐng)輸入一個(gè)整數(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("算法用時(shí)%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("輸入有誤！請(qǐng)重新輸入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-)/比較,找出本趟最小關(guān)鍵字的記錄if (Rj.key<Rj-1.key) tmp=Rj; /Rj與Rj-1進(jìn)行交換,將最小關(guān)鍵字記錄前移Rj=Rj-1;Rj-1=tmp;finish=clock();duration=(double)(finish-start)/CLOCKS_PER_SEC;printf("冒泡排序已經(jīng)完成！n");printf("算法用時(shí)%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調(diào)整到雙親結(jié)點(diǎn)位置上i=j; /修改i和j值,以便繼續(xù)向下篩選j=2*i; else break; /篩選結(jié)束Ri=temp; /被篩選結(jié)

14、點(diǎn)的值放入最終位置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、"算法用時(shí)%f秒nn",duration);Writefile(R,n,2);/*Insertsort.c*/#include"Head.h"void InsertSort(RecType R,int n) /對(duì)R0.n-1按遞增有序進(jìn)行直接插入排序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; /將關(guān)鍵字大于Ri.key的記錄后移j-;Rj+1=tmp; /在j+1處插入Rifinish=clock();duration=(double)(finish-start)/CLOCKS_PER_SEC;printf("插入排序已經(jīng)完成！n");printf("算法用時(shí)%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的下標(biāo),i、j分別為第1、2段的下標(biāo)R1=(RecType *)malloc(high-low+1)*sizeof(RecType); /動(dòng)態(tài)分配空間while (i<=mid && j<=high) /在第1段和第2段均未掃描完時(shí)循環(huán)if (Ri.key<=Rj.key) /將第1段中的記錄放入R1中R1k=Ri;i+;k+; else /將第2段中的記錄放入R1中R1k=Rj;j+;k+;while (i<=mid) /將第1段余下部分復(fù)制到R1R1

18、k=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) /對(duì)整個(gè)數(shù)序進(jìn)行一趟歸并int i;for (i=0; i+2*length-1<n; i=i+2*length) /歸并length長(zhǎng)的兩相鄰子表Merge(R,i,i+length-1,i+2*length-1);if (i+length-1<n) /余下兩個(gè)子表,后者長(zhǎng)度小于le

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

20、并排序已經(jīng)完成！n");printf("算法用時(shí)%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("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) /對(duì)Rs至Rt的元素進(jìn)行快速排序int i=s,j=t;RecType tmp;if (s<t) /區(qū)間內(nèi)至少存在兩個(gè)元素的情況tmp=Rs; /用區(qū)間的第1個(gè)記錄作為基準(zhǔn)while (i!=j) /從區(qū)間兩端交替向中間掃描,直至i=j為止while (j>i && Rj.key>=tmp.key) j-; /從右向左掃描,

27、找第1個(gè)小于tmp.key的RjRi=Rj;/找到這樣的Rj,Ri"Rj交換while (i<j && Ri.key<=tmp.key) i+;/從左向右掃描,找第1個(gè)大于tmp.key的記錄RiRj=Ri;/找到這樣的Ri,Ri"Rj交換Ri=tmp;QuickSort(R,s,i-1); /對(duì)左區(qū)間遞歸排序QuickSort(R,i+1,t); /對(duì)右區(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+) /在當(dāng)前無(wú)序區(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)(finish-start)/CLOCKS_PER_SEC;printf("選

29、擇排序已經(jīng)完成！n");printf("算法用時(shí)%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+) /對(duì)所有相隔gap位置的所有

30、元素組進(jìn)行排序tmp=Ri;j=i-gap;while (j>=0 && tmp.key<Rj.key) /對(duì)相隔gap位置的元素組進(jìn)行排序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("算法用時(shí)%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("隨機(jī)函數(shù)產(chǎn)生的隨機(jī)序列如下：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("提示：排序結(jié)果已保存至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("提示：排序結(jié)果已保存至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("提示：排序結(jié)果已保存至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("提示：排序結(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),fp);fclose(fp);printf("提示：排序結(jié)果已保存至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("提示：排序結(jié)果已保存至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("提示：排序結(jié)果已保存至ShellSort.datn");break;4、 調(diào)試分析 圖1 菜單界面 圖2 輸入整數(shù)1，產(chǎn)生20000個(gè)隨機(jī)數(shù) 圖3 輸入2，插入排序 圖4 輸入3，冒泡排序 圖5 輸入4，希爾排序 圖6 輸入5，快速排序 圖7 輸入6，選擇排序 圖8 輸入7，堆排序圖9 輸入8，歸并排序圖10至圖16為輸入9后從文件打印出來(lái)的排序結(jié)果 圖10 圖11 圖12 圖13圖14圖15圖16圖17 輸入整數(shù)11，退出程序課程設(shè)計(jì)總結(jié)1、 調(diào)試過(guò)程中遇到的問(wèn)題是如何解決的，以及對(duì)設(shè)計(jì)與實(shí)現(xiàn)的回顧討論與分析。我一開(kāi)始先按照書(shū)本的介紹，將7個(gè)排序算法寫(xiě)好，然后再去設(shè)計(jì)主函數(shù)來(lái)調(diào)用這些排序算法。在