数据结构排序综合

1、目 录1.需求分析12.概要设计13.详细设计24.测试分析19课程设计总结22参 考 文 献24一、需求分析问题描述：此次的任务是利用随机函数产生N个随机整数，对这些数进行多种方法进行排序，分别是插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中。然后统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。基本要求：数据输入的形式和输入值的范围：设定的随机数据的范围是0到30000，产生30000个，类型均为整型。数据输出的形式：程序以一个排序完成后的有序数组来输出。程序所设计的功能：（1）构建菜单，为

2、每种排序方法设定一个选项数字，用户可根据需要选择不同的排序方法。可以选择的方法有：插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序共七种。（2） 每种排序结束后自动计算该排序的耗时。（3） 将排序后的数据保存到相应的文件里面。（4）数据由随机函数产生。二、概要设计为了实现需求分析中的功能，可以从以下3个方面着手设计。1、 主界面设计利用switch函数设计出菜单，即通过case分别调用不同的排序方法。2、存储结构设计本次存储结构仅用到了数组的储存结构。原因：需要存储的数据是连续的，数据类型也只有一种，所以用数组的存储结构能合理利用存储空间。而且我们所学的排序算法是基于数组的储

3、存结构实现的。3、 系统功能设计Head.h：用于声明必要的头文件，函数及结构体Srand.c：用于产生随机数Writefile.c：用于将排序结果存入文件Print.c：用于输出文件中的排序结果Insertsort.c：用于将产生的随机数进行插入排序Shellsort.c：用于将产生的随机数进行希尔排序Bubblesort.c：用于将产生的随机数进行冒泡排序Quicksort.c：用于将产生的随机数进行快速排序Selectsort.c：用于将产生的随机数进行选择排序Heapsort.c：用于将产生的随机数进行堆排序Mergesort.c：用于将产生的随机数进行归并排序4、 各个程序模块之间的

4、层次（调用）关系：三、详细设计1、数据类型设计：typedef int KeyType; /定义关键字类型typedef char InfoType10;typedef struct /记录类型KeyType key; /关键字项InfoType data; /其他数据项,类型为InfoType RecType;2、 详细算法：头文件：/*Head.h*/#include#include #include #define MaxSize 20000typedef int KeyType; /定义关键字类型typedef char InfoType10;typedef struct /记录类型K

5、eyType key; /关键字项InfoType data; /其他数据项,类型为InfoType RecType;/排序的记录类型定义void InsertSort(RecType R,int n);/1.插入排序 void Srand(RecType R);/随机函数 void print(RecType R,int a);/打印函数 void BubbleSort(RecType R,int n);/2.冒泡排序 void ShellSort(RecType R,int n);/3.希尔排序 void QuickSort(RecType R,int s,int t);/4.快速排序 v

6、oid 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*/#includeHead.hRecType RMaxSize,R1MaxSize+1;void Menu() int i;clock_t start,finish;double duration;int a,n=MaxSize;printf( 1.

7、产生随机数n);printf( 2.插入排序n);printf( 3.冒泡排序n);printf( 4.希尔排序n);printf( 5.快速排序n);printf( 6.选择排序n);printf( 7.堆排序n);printf( 8.归并排序n);printf( 9.打印各种排序方法排序后的序列n);printf( 10.清空屏幕n);printf( 11.结束程序n);fflush(stdin);printf(请输入一个整数：);scanf(%d,&a);printf(n);fflush(stdin);switch(a) case 1:Srand(R);break;case 2:for

8、(i=0; iMaxSize; i+)R1i.key=Ri.key;InsertSort(R1,n);break;case 3:for (i=0; iMaxSize; i+)R1i.key=Ri.key;BubbleSort(R1,n);break;case 4:for (i=0; iMaxSize; i+)R1i.key=Ri.key;ShellSort(R1,n);break;case 5:for (i=0; iMaxSize; i+)R1i.key=Ri.key;start =clock();QuickSort(R1,0,n-1);finish=clock();duration=(dou

9、ble)(finish-start)/CLOCKS_PER_SEC;printf(快速排序已经完成！n);printf(算法用时%f秒nn,duration);Writefile(R1,n,5);break;case 6:for (i=0; iMaxSize; i+)R1i.key=Ri.key;SelectSort(R1,n);break;case 7:for (i=0; iMaxSize; i+)R1i+1.key=Ri.key;Heapsort(R1,n);break;case 8:for (i=0; iMaxSize; i+)R1i.key=Ri.key;MergeSort(R1,n)

10、;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*/#includeHead.hvoid BubbleSort(RecType R,int n) int i,j,k;RecType tmp;clock_t start,finish;double duration;start =clock();for (i=0; ii; j-

11、)/比较,找出本趟最小关键字的记录if (Rj.keyRj-1.key) tmp=Rj; /Rj与Rj-1进行交换,将最小关键字记录前移Rj=Rj-1;Rj-1=tmp;finish=clock();duration=(double)(finish-start)/CLOCKS_PER_SEC;printf(冒泡排序已经完成！n);printf(算法用时%f秒nn,duration);Writefile(R,n,1);/*Heapsort.c*/#includeHead.hvoid sift(RecType R,int low,int high) int i=low,j=2*i; /Rj是Ri的

12、左孩子RecType temp=Ri;while (j=high) if (jhigh & Rj.keyRj+1.key) /若右孩子较大,把j指向右孩子j+; /变为2i+1if (temp.key=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(堆排序已经完成！n);printf(算法用时%f秒nn,duration);Writefile(R,n,2);/*Ins

13、ertsort.c*/#includeHead.hvoid 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=0 & tmp.keyRj.key) Rj+1=Rj; /将关键字大于Ri.key的记录后移j-;Rj+1=tmp; /在j+1处插入Rifinish=clock();duration=(double)(finish-start)/CLOCKS_PER_SEC;prin

14、tf(插入排序已经完成！n);printf(算法用时%f秒nn,duration);Writefile(R,n,3);/*Mergesort.c*/#includeHead.hvoid 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); /动态分配空间while (i=mid & j=high) /在第1段和第2段均未扫描完时循环if (Ri.key

15、=Rj.key) /将第1段中的记录放入R1中R1k=Ri;i+;k+; else /将第2段中的记录放入R1中R1k=Rj;j+;k+;while (i=mid) /将第1段余下部分复制到R1R1k=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) /对整个数序进行一趟归并int i;for (i=0; i+2*length-1n; i=i+2*length) /

16、归并length长的两相邻子表Merge(R,i,i+length-1,i+2*length-1);if (i+length-1n) /余下两个子表,后者长度小于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; lengthn; length=2*length) /进行log2n趟归并MergePass(R,length,

17、n);finish=clock();duration=(double)(finish-start)/CLOCKS_PER_SEC;printf(归并排序已经完成！n);printf(算法用时%f秒nn,duration);Writefile(R,n,4);/*Print.c*/#includeHead.hvoid print(RecType R,int a) FILE *fp;int i;RecType R2MaxSize+1;/用于从文件输出保存结果i=0;printf(排序结果如下：n);printf(插入排序：n);fp=fopen(Resultfile/InsertSort.dat,r

18、b);while(fread(&R2i.key,sizeof(int),1,fp)=1)i+;fclose(fp);for(i=0; iMaxSize; 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);for(i=0; iMaxSize; i+)printf(%d ,R2i.key);printf(n);i=0;printf(冒泡排序：n);fp=fope

19、n(Resultfile/BubbleSort.dat,rb);while(fread(&R2i.key,sizeof(int),1,fp)=1)i+;fclose(fp);for(i=0; iMaxSize; i+)printf(%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; iMaxSize; i+)printf(%d ,R2i.key);printf(

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

21、+)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; iMaxSize; i+)printf(%d ,R2i.key);printf(n);/*Quicksort.c*/#includeHead.hvoid QuickSort(RecType R,int s,int t) /对Rs至Rt的元素进行快速排序int i=s,j=t;RecType t

22、mp;if (si & Rj.key=tmp.key) j-; /从右向左扫描,找第1个小于tmp.key的RjRi=Rj;/找到这样的Rj,RiRj交换while (ij & Ri.key=tmp.key) i+;/从左向右扫描,找第1个大于tmp.key的记录RiRj=Ri;/找到这样的Ri,RiRj交换Ri=tmp;QuickSort(R,s,i-1); /对左区间递归排序QuickSort(R,i+1,t); /对右区间递归排序/*Selectsort.c*/#includeHead.hvoid SelectSort(RecType R,int n)int i,j,k,l;RecTyp

23、e temp;clock_t start,finish;double duration;start =clock();for (i=0;in-1;i+) /做第i趟排序k=i;for (j=i+1;jn;j+) /在当前无序区Ri.n-1中选key最小的Rkif (Rj.key0) for (i=gap; i=0 & tmp.keyRj.key) /对相隔gap位置的元素组进行排序Rj+gap=Rj;j=j-gap;Rj+gap=tmp;j=j-gap;gap=gap/2;/减小增量finish=clock();duration=(double)(finish-start)/CLOCKS_PE

24、R_SEC;printf(希尔排序已经完成！n);printf(算法用时%f秒nn,duration);Writefile(R,n,7);/*Srand.c*/#includeHead.hvoid Srand(RecType R) int i;time_t t;srand(unsigned) time(&t);printf(随机函数产生的随机序列如下：n);for (i=0; iMaxSize; i+)printf(%d ,Ri.key=(rand()%MaxSize);printf(nnn);/*Writefile.c*/#includeHead.hvoid Writefile(RecTyp

25、e R1,int n,int k) int i;FILE *fp;switch(k) case 1:if(fp=fopen(Resultfile/BubbleSort.dat,wb)=NULL) printf(t提示：不能创建文件n);return;for(i=0; in; i+) fwrite(&R1i.key,1,sizeof(int),fp);fclose(fp);printf(提示：排序结果已保存至BubbleSort.datn);break;case 2:if(fp=fopen(Resultfile/Heapsort.dat,wb)=NULL) printf(t提示：不能创建文件n)

26、;return;for(i=1; in+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提示：不能创建文件n);return;for(i=0; in; i+) fwrite(&R1i.key,1,sizeof(int),fp);fclose(fp);printf(提示：排序结果已保存至InsertSort.datn);break;case

27、 4:if(fp=fopen(Resultfile/MergeSort.dat,wb)=NULL) printf(t提示：不能创建文件n);return;for(i=0; in; i+) fwrite(&R1i.key,1,sizeof(int),fp);fclose(fp);printf(提示：排序结果已保存至MergeSort.datn);break;case 5:if(fp=fopen(Resultfile/QuickSort.dat,wb)=NULL) printf(t提示：不能创建文件n);return;for(i=0; in; i+) fwrite(&R1i.key,1,sizeo

28、f(int),fp);fclose(fp);printf(提示：排序结果已保存至QuickSort.datn);break;case 6:if(fp=fopen(Resultfile/SelectSort.dat,wb)=NULL) printf(t提示：不能创建文件n);return;for(i=0; in; i+) fwrite(&R1i.key,1,sizeof(int),fp);fclose(fp);printf(提示：排序结果已保存至SelectSort.datn);break;case 7:if(fp=fopen(Resultfile/ShellSort.dat,wb)=NULL)

29、 printf(t提示：不能创建文件n);return;for(i=0; in; i+) fwrite(&R1i.key,1,sizeof(int),fp);fclose(fp);printf(提示：排序结果已保存至ShellSort.datn);break;4、 调试分析 图1 菜单界面 图2 输入整数1，产生20000个随机数 图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

30、 输入整数11，退出程序课程设计总结1、 调试过程中遇到的问题是如何解决的，以及对设计与实现的回顾讨论与分析。我一开始先按照书本的介绍，将7个排序算法写好，然后再去设计主函数来调用这些排序算法。在这个过程中，我遇到了很多麻烦。第一，将每个算法单独变成.c文件独立出来后，函数的声明方式和变量的传递方法困扰了我好久，后来我通过设计一个头文件的方式包含了所有需要声明的头文件和程序要用到的函数，然后把这个头文件放到每个子程序中，问题得到了解决。第二，我发现产生的随机数只能用于一次排序，没有把随机序列保存下来，后来又设计算法来复制产生的随机数列。第三，对于程序中需要用到的库函数，我去网上查找了很多资料才学会怎么用，说明平时掌握的函数还不够多，不熟练。设计排序算法的过程中，我在快速排序和堆