综合排序数据结构课程设计

1、题 目：综合排序-数据结构课程设计 院 系：信息工程学院专 业：计算机科学与技术班 级：姓 名：学 号：指导老师:时 间：目录一、问题描述4二、内容简介42.1 基本要求：42.2. 算法思想：42.3. 模块划分：42.4. 数据结构：52.5. 源程序：52.6. 测试情况：14三、小结17一、 问题描述利用随机函数产生n个随机整数（20000以上），对这些数进行多种方法进行排序。要求：1) 至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中。2) 统计每一种排序方法的性能（以上机运

2、行程序所花费的时间为准进行对比），找出其中两种较快的方法。3) 如果采用4种或4种以上的方法者，可适当加分。二、 内容简介2.1 基本要求：（1） 设计一个的菜单将在实现的功能显示出来，并有选择提示（2） 分别实现直接插入排序、折半插入排序、希尔排序、冒泡排序、快速排序、简单排序、堆排序算法；（3） 通过多种测试数据，对各种排序算法的时间复杂度和空间复杂度进行比较2.2. 算法思想：1.处理流程图开始直接插入排序时间效率比较直接选择排序显示菜单冒泡排序快速排序堆排序显示随机数显示排序后的的数据和时间效率输入序号结束退出随机数显示各个排序法对同一组数据排序所用的时间和其中两种较快的方法12345

3、670void bublesort(double a)时间数组的冒泡排序void insertsort(int a,int p)void selectsort(int a,int p)void disp(int a)void creatheap(int a,int i,int n) void heapsort(int a,int n,int p)double tinsertsort(int a,int p)void quicksort(int a,int n, int p)void bubblesort(int a,int p)double tselectsort(int a,int p)do

4、uble tquicksort(int a,int left, int right,int p)double tbubblesort(int a,int p)double theapsort(int a,int n,int p)3.设计一个高精度时间函数，分别测试各种排序的时间消耗；4.在主函数中，用开关语句swtich()case 值1;break;case值n;break;default语句序列:n+1;调用各种排序算法，各种排序的时间消耗函数，从而在屏幕上输出供选择的菜单，各种排序时间和空间复杂度的比较。2.3. 模块划分：1.输入初始数据函数：int makelist(recnode

5、*r) 2.输出未排序前的数据函数：void undealoutlist(recnode *r,int n) 3.处理后的序列函数：void dealoutlist(recnode*r,int n) 4.这种排序的算法：void insertsort(recnode*r,int n)/直接插入排序void biinsertionsort (recnode*r, int n) / 折半插入排序void bublesort(recnode *r,int n) /冒泡排序int partition(recnode*r,int*low,int*high)/一趟快速排序void quicksort(re

6、cnode*r,int start,int end)/快速排序void selesort(recnode*r,int n)/直接选择排序void shellsort(recnode *r,int n)/希尔排序void sift(recnode*r,int i,int m)void heapsort(recnode*r,int n)/堆排序5.排序时间测试函数：double tinsertsort(int len,recnode *a,int p)2.4. 数据结构：1.预定义常量和自定义类型：#define maxsize 100 typedef struct int key; recnod

7、e;2.基本函数的算法用以下形式表示：函数类型 函数名（函数参数表）/算法说明 语句序列/函数名。3.定义 int b,t,i,j; /b为记录交换的次数，t为记录排序的趟数,i为排序的数据，j为暂存数据的临时变量。4. 输入初始数据函数中定义int k, j，k为输入数据个数，j为输入的数据。5.快速排序中定义static int w=0,int *low，*high。6.在直接选择排序中定义int z，临时储存i的值。7.在希尔排序中定义int dk，记录前后位置的增量。8.在排序时间消耗测试的函数和主函数中定义了int p，为菜单的序号。9.在主函数中定义int len，为测试数据的总长

8、度。2.5. 源程序：插入排序核心代码void insertsort(int a,int p) int i,j,temp; for(i=1;i0&aj-1temp;j-) aj=aj-1; aj=temp; 选择排序核心代码void selectsort(int a,int p) int i,j,k; for(i=0;in-1;i+) k=i; for(j=i+1;jn;j+) if(ajak) k=j; if(k!=i) int temp; temp=ak; ak=ai; ai=temp; 冒泡排序算法核心代码void bubblesort(int a,int p) int i,j,temp

9、; for (i=0;ii;j-) /*比较,找出本趟最小关键字的记录*/ if (ajaj-1) temp=aj; /*进行交换,将最小关键字记录前移*/ aj=aj-1; aj-1=temp; 创建堆核心代码void creatheap(int a,int i,int n) int j;int t;t=ai;j=2*(i+1)-1;while(j=n)if(jn)&(ajaj+1)j+;if(t=0;i-)creatheap(a,i,n-1);for(i=n-1;i=1;i-)t=a0;a0=ai;ai=t;creatheap(a,0,i-1);快速排序核心代码void quicksort

10、(int a,int n,int p) int i,j,low,high,temp,top=-1; struct node int low,high; stn; top+; sttop.low=0;sttop.high=n-1; while(top-1) low=sttop.low;high=sttop.high; top-; i=low;j=high; if(lowhigh) temp=alow; while(i!=j) while(itemp)j-; if(ij)ai=aj;i+; while(ij&aitemp)i+; if(ij)aj=ai;j-; ai=temp; top+;stto

11、p.low=low;sttop.high=i-1; top+;sttop.low=i+1;sttop.high=high; 时间部分代码double tinsertsort(int a,int p)int i;int bn; for(i=0;in;i+) bi=ai;large_integer m_liperffreq=0;queryperformancefrequency(&m_liperffreq); large_integer m_liperfstart=0; queryperformancecounter(&m_liperfstart);insertsort(b,p);large_in

12、teger liperfnow=0; queryperformancecounter(&liperfnow); double time=liperfnow.quadpart - m_liperfstart.quadpart; time/=m_liperffreq.quadpart;if(p!=6)disp(b);getchar();printf(n用直接插入排序法用的时间为%f秒；,time);file *fp; fp=fopen(直接插入排序.txt,w); for(i=0;in;i+) fprintf(fp,%d ,bi); fclose(fp);return(time);double t

13、selectsort(int a,int p)int i;int bn;for(i=0;in;i+)bi=ai;large_integer m_liperffreq=0;queryperformancefrequency(&m_liperffreq); large_integer m_liperfstart=0; queryperformancecounter(&m_liperfstart);selectsort(b,p);if(p!=6)disp(b);getchar();large_integer liperfnow=0; queryperformancecounter(&liperfno

14、w); double time=liperfnow.quadpart - m_liperfstart.quadpart; time/=m_liperffreq.quadpart;printf(n用直接选择排序法用的时间为%f秒；,time);file *fp; fp=fopen(直接选择排序.txt,w);for(i=0;in;i+) fprintf(fp,%d ,bi);fclose(fp);return(time);double tbubblesort(int a,int p)int i;int bn;for(i=0;in;i+)bi=ai;large_integer m_liperffr

15、eq=0;queryperformancefrequency(&m_liperffreq); large_integer m_liperfstart=0; queryperformancecounter(&m_liperfstart);bubblesort(b,p);large_integer liperfnow=0; queryperformancecounter(&liperfnow); double time=liperfnow.quadpart - m_liperfstart.quadpart; time/=m_liperffreq.quadpart;if(p!=6)disp(b);g

16、etchar();printf(n用冒泡排序法用的时间为%f秒；,time);file *fp; fp=fopen(冒泡排序.txt,w); for(i=0;in;i+) fprintf(fp,%d ,bi);fclose(fp);return(time);double theapsort(int a,int n,int p) int i;int bn;for(i=0;in;i+)bi=ai;large_integer m_liperffreq=0;queryperformancefrequency(&m_liperffreq); large_integer m_liperfstart=0;

17、queryperformancecounter(&m_liperfstart);heapsort(b,n,p);large_integer liperfnow=0; queryperformancecounter(&liperfnow); double time=liperfnow.quadpart - m_liperfstart.quadpart; time/=m_liperffreq.quadpart;if(p!=6)disp(b);getchar();printf(n用堆排序法用的时间为%f秒；,time);file *fp; fp=fopen(堆排序.txt,w);for(i=0;in

18、;i+) fprintf(fp,%d ,bi);fclose(fp);return(time);double tquicksort(int a,int n,int p)int i;int bn; for(i=0;in;i+) bi=ai;large_integer m_liperffreq=0;queryperformancefrequency(&m_liperffreq); large_integer m_liperfstart=0; queryperformancecounter(&m_liperfstart);quicksort(b,n,p);large_integer liperfno

19、w=0; queryperformancecounter(&liperfnow); double time=liperfnow.quadpart - m_liperfstart.quadpart; time/=m_liperffreq.quadpart;if(p!=6) disp(b);getchar(); printf(n用快速排序法用的时间为%f秒；,time);file *fp;fp=fopen(快速排序.txt,w); for(i=0;in;i+) fprintf(fp,%d ,bi); fclose(fp); return(time);时间数组的冒泡排序void bublesort(

20、double a) int i,j; double temp; for(i=1;i=i;j-) if(aj+1请在上述序号中选择一个并输入:);主函数代码void main() int i,p,an; srand(int)time(null); /*随机种子*/ for(i=0;i谢谢使用!n); getchar(); break; double times5,times15;/时间数组 switch(p) case 1:tinsertsort(a,p);printf(n请按任意键继续.);getchar();break; case 2:tselectsort(a,p);printf(n请按任

21、意键继续.);getchar();break; case 3:tbubblesort(a,p);printf(n请按任意键继续.);getchar();break; case 4:tquicksort(a,n,p);printf(n请按任意键继续.);getchar();break; case 5:theapsort(a,n,p);printf(n请按任意键继续.);getchar();break; case 6:system(cls);times11=times1=tinsertsort(a,p);times12=times2=tselectsort(a,p); times13=times3

22、=tbubblesort(a,p);times14=times4=tquicksort(a,n,p);times15=times5=theapsort(a,n,p);getchar(); bublesort(times); printf(nn); printf(排序这组数据两种较快的排序法分别是：n); if(times1=times11) printf(直接插入排序:%f秒!n,times1); if(times1=times12) printf(直接选择排序:%f秒!n,times1); if(times1=times13) printf(冒泡排序:%f秒!n,times1); if(times1=times14) printf(快速排序:%f秒!n,times1); if(times1=times15) printf(堆排序:%f秒!n,times1); if(times1!=times2) if(times2=times11) printf(直接插入排序:%f秒!n,times2); if(times2=times12) printf(直接选择排序%f秒!n,times2); if(times2=times13) printf(冒泡排序%f秒!n,times2);