数据结构排序综合

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<stdio.h>#include <stdlib.h>#include <time.h>#define MaxSize 20000typedef int KeyType; /定义关键字类型

5、typedef char InfoType10;typedef struct /记录类型KeyType 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.希尔排序 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.产生随机数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("请输入一个整数：");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("快速排序已经完成

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("冒泡排序已经完成！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+; /变为2i+1if (temp.key<Rj.key) Ri=Rj; /将Rj调整到双亲结点位置上i=j; /修改i和j值,以便继续向下筛选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("堆排序已经完成！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; /从右向左在有序区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("插入排序已经完成！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); /动态分配空间while (i<=mid && j<=high) /在第1段和第2段均未扫描完时循环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) /对整个数序进行一趟归并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) /进行log2n趟归并MergePass(R,length,n);finish=clock();duration=(double)(finish-start)/CLOCKS_PER_SEC;printf("归

20、并排序已经完成！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) /区间内至少存在两个元素的情况tmp=Rs; /用区间的第1个记录作为基准while (i!=j) /从区间两端交替向中间扫描,直至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); /对左区间递归排序QuickSort(R,i+1,t); /对右区间递归排序/*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+) /在当前无序区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、择排序已经完成！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("希尔排序已经完成！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("随机函数产生的随机序列如下：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提示：不能创建文件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提示：不能创建文件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、提示：不能创建文件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提示：不能创建文件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提示：不能创建文件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提示：不能创建文件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提示：不能创建文件n");return;for(i=0; i<n; 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 输入整数11，退出程序课程设计总结1、 调试过程中遇到的问题是如何解决的，以及对设计与实现的回顾讨论与分析。我一开始先按照书本的介绍，将7个排序算法写好，然后再去设计主函数来调用这些排序算法。在