《综合排序数据结构课程设计.docx》由会员分享，可在线阅读，更多相关《综合排序数据结构课程设计.docx（25页珍藏版）》请在三一办公上搜索。
1、题 目：综合排序-数据结构课程设计 院 系：信息工程学院专 业：运算机科学与技术班 级：姓 名：学 号：指导老师:时 间：目录一、问题描述8二、内容简介9大体要求：9. 算法思想：9. 模块划分：11. 数据结构：11. 源程序：12插入排序核心代码12void InsertSort(int a,int p)12int i,j,temp;12for(i=1;i0&aj-1temp;j-)12aj=aj-1;12aj=temp;121212选择排序核心代码12void SelectSort(int a,int p)1212int i,j,k;12for(i=0;iN-1;i+)1212k=i;1
2、2for(j=i+1;jN;j+)12if(ajak)12k=j;12if(k!=i)1212int temp;12temp=ak;13ak=ai;13ai=temp;13131313冒泡排序算法核心代码13void BubbleSort(int a,int p)1313int i,j,temp;13for (i=0;ii;j-) /*比较,找出本趟最小关键字的记录*/13if (ajaj-1)1313temp=aj; /*进行互换,将最小关键字记录前移*/13aj=aj-1;13aj-1=temp;13131313创建堆核心代码13void creatheap(int a,int i,int
3、 n) 13int j;13int t;13t=ai;13j=2*(i+1)-1;13while(j=n)1313if(jn)&(ajaj+1)13j+;13if(t=0;i-)14creatheap(a,i,n-1);14for(i=n-1;i=1;i-)1414t=a0;14a0=ai;14ai=t;14creatheap(a,0,i-1);1414快速排序核心代码14void quicksort(int a,int n,int p)1414int i,j,low,high,temp,top=-1;14struct node1414int low,high;14stN;14top+;14s
4、ttop.low=0;sttop.high=n-1;14while(top-1)14 low=sttop.low;high=sttop.high;14top-;14i=low;j=high;14if(lowhigh)14 temp=alow;14while(i!=j)14 while(itemp)j-;14if(ij)ai=aj;i+;14while(ij&aitemp)i+;14if(ij)aj=ai;j-;1414ai=temp;14top+;sttop.low=low;sttop.high=i-1;15top+;sttop.low=i+1;sttop.high=high;15151515
5、时刻部份代码15double TInsertSort(int a,int p)1515int i;15int bN;15for(i=0;iN;i+)15bi=ai;15LARGE_INTEGER m_liPerfFreq=0;15QueryPerformanceFrequency(&m_liPerfFreq);15LARGE_INTEGER m_liPerfStart=0;15QueryPerformanceCounter(&m_liPerfStart);15InsertSort(b,p);15LARGE_INTEGER liPerfNow=0;15QueryPerformanceCounte
6、r(&liPerfNow);15double time= - ;15time/=;15if(p!=6)15Disp(b);getchar();15printf(n用直接插入排序法用的时刻为%f秒；,time);15FILE *fp;15fp=fopen(直接插入排序.txt,w);15for(i=0;iN;i+)15fprintf(fp,%d ,bi);15fclose(fp);15return(time);1515double TSelectSort(int a,int p)1515int i;15int bN;15for(i=0;iN;i+)15bi=ai;15LARGE_INTEGER
7、m_liPerfFreq=0;15QueryPerformanceFrequency(&m_liPerfFreq);15LARGE_INTEGER m_liPerfStart=0;15QueryPerformanceCounter(&m_liPerfStart);15SelectSort(b,p);15if(p!=6)15Disp(b);getchar();16LARGE_INTEGER liPerfNow=0;16QueryPerformanceCounter(&liPerfNow);16double time= - ;16time/=;16printf(n用直接选择排序法用的时刻为%f秒；
8、,time);16FILE *fp;16fp=fopen(直接选择排序.txt,w);16for(i=0;iN;i+)16fprintf(fp,%d ,bi);16fclose(fp);return(time);1616double TBubbleSort(int a,int p)1616int i;16int bN;16for(i=0;iN;i+)16bi=ai;16LARGE_INTEGER m_liPerfFreq=0;16QueryPerformanceFrequency(&m_liPerfFreq);16LARGE_INTEGER m_liPerfStart=0;16QueryPer
9、formanceCounter(&m_liPerfStart);16BubbleSort(b,p);16LARGE_INTEGER liPerfNow=0;16QueryPerformanceCounter(&liPerfNow);16double time= - ;16time/=;16if(p!=6)16Disp(b);getchar();16printf(n用冒泡排序法用的时刻为%f秒；,time);16FILE *fp;16fp=fopen(冒泡排序.txt,w);16for(i=0;iN;i+)16fprintf(fp,%d ,bi);16fclose(fp);return(time
10、);1616double Theapsort(int a,int n,int p)1616int i;16int bN;16for(i=0;iN;i+)16bi=ai;17LARGE_INTEGER m_liPerfFreq=0;17QueryPerformanceFrequency(&m_liPerfFreq);17LARGE_INTEGER m_liPerfStart=0;17QueryPerformanceCounter(&m_liPerfStart);17heapsort(b,N,p);17LARGE_INTEGER liPerfNow=0;17QueryPerformanceCoun
11、ter(&liPerfNow);17double time= - ;17time/=;17if(p!=6)17Disp(b);getchar();17printf(n用堆排序法用的时刻为%f秒；,time);17FILE *fp;17fp=fopen(堆排序.txt,w);17for(i=0;iN;i+)17fprintf(fp,%d ,bi);17fclose(fp);return(time);1717double Tquicksort(int a,int n,int p)1717int i;17int bN;17for(i=0;iN;i+)17bi=ai;17LARGE_INTEGER m
12、_liPerfFreq=0;17QueryPerformanceFrequency(&m_liPerfFreq);17LARGE_INTEGER m_liPerfStart=0;17QueryPerformanceCounter(&m_liPerfStart);17quicksort(b,N,p);17LARGE_INTEGER liPerfNow=0;17QueryPerformanceCounter(&liPerfNow);17double time= - ;17time/=;17if(p!=6)17Disp(b);getchar(); 17printf(n用快速排序法用的时刻为%f秒；,
13、time);17FILE *fp;fp=fopen(快速排序.txt,w);17for(i=0;iN;i+)17fprintf(fp,%d ,bi);17fclose(fp); return(time);1718时刻数组的冒泡排序18void BubleSort(double a)1818int i,j;18double temp;18for(i=1;i=i;j-)18if(aj+1请在上述序号当选择一个并输入:);1919主函数代码19void main()1919int i,p,aN;19srand(int)time(NULL); /*随机种子*/19for(i=0;i谢谢利用!n);19
14、getchar();19break;1919double TIMES5,TIMES15;.);getchar();break;19case 2:TSelectSort(a,p);printf(n请按任意键继续.);getchar();break;19case 3:TBubbleSort(a,p);printf(n请按任意键继续.);getchar();break;19case 4:Tquicksort(a,N,p);printf(n请按任意键继续.);getchar();break;19case 5:Theapsort(a,N,p);printf(n请按任意键继续.);getchar();br
15、eak;19case 6:system(cls);19TIMES11=TIMES1=TInsertSort(a,p);TIMES12=TIMES2=TSelectSort(a,p);19TIMES13=TIMES3=TBubbleSort(a,p);TIMES14=TIMES4=Tquicksort(a,N,p);TIMES15=TIMES5=Theapsort(a,N,p);getchar();19BubleSort(TIMES);19printf(nn);1919printf(排序这组数据两种较快的排序法别离是：n);19if(TIMES1=TIMES11) printf(直接插入排序:%
16、f秒!n,TIMES1);19if(TIMES1=TIMES12) printf(直接选择排序:%f秒!n,TIMES1);19if(TIMES1=TIMES13) printf(冒泡排序:%f秒!n,TIMES1);19if(TIMES1=TIMES14) printf(快速排序:%f秒!n,TIMES1);19if(TIMES1=TIMES15) printf(堆排序:%f秒!n,TIMES1);20if(TIMES1!=TIMES2)2020if(TIMES2=TIMES11) printf(直接插入排序:%f秒!n,TIMES2);20if(TIMES2=TIMES12) printf
17、(直接选择排序%f秒!n,TIMES2);20if(TIMES2=TIMES13) printf(冒泡排序%f秒!n,TIMES2);20if(TIMES2=TIMES14) printf(快速排序%f秒!n,TIMES2);20if(TIMES2=TIMES15) printf(堆排序%f秒!n,TIMES2);2020 printf(n请按任意键继续.);srand(int)time(NULL);20for(i=0;iN;i+) ai=rand()%30000+1; getchar();break;20case 7:Disp(a);FILE *fp;fp=fopen(随机数.txt,w);
18、20for(i=0;iN;i+)fprintf(fp,%d ,ai);fclose(fp);getchar();printf(n请按任意键继续.);getchar();break;20default:Wrong();printf(n请按任意键继续.);getchar();break;20202020. 测试情形：20三、小结23一、 问题描述利用随机函数产生N个随机整数（20000以上），对这些数进行多种方式进行排序。要求：1) 至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中。2)
19、统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。3) 如果采用4种或4种以上的方法者，可适当加分。二、 内容简介 大体要求：（1） 设计一个的菜单将在实现的功能显示出来，并有选择提示（2） 别离实现直接插入排序、折半插入排序、希尔排序、冒泡排序、快速排序、简单排序、堆排序算法；（3） 通过量种测试数据，对各类排序算法的时刻复杂度和空间复杂度进行比较. 算法思想：1.处置流程图开始直接插入排序时间效率比较直接选择排序显示菜单冒泡排序快速排序堆排序显示随机数显示排序后的的数据和时间效率输入序号结束退出随机数显示各个排序法对同一组数据排序所用的时间和其中两
20、种较快的方法12345670void 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
21、 a,int p)double 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;挪用各类排序算法，各类排序的时刻消耗函数，从而在屏幕上输出供选择的菜单，各类排序时刻和空间复杂度的比较。. 模块划分：1.输入初始数据函数：int MakeList(
22、RECNODE *r) 2.输出未排序前的数据函数：void UndealoutList(RECNODE *r,int n) 3.处置后的序列函数：void DealoutList(RECNODE*r,int n) 4.这种排序的算法：void InsertSort(RECNODE*r,int n)序时刻测试函数：double TInsertSort(int len,RECNODE *a,int p). 数据结构：1.预概念常量和自概念类型：#define MAXSIZE 100 typedef struct int key; RECNODE;2.大体函数的算法用以下形式表示：函数类型 函数名
23、（函数参数表）义 int b,t,i,j; 输入初始数据函数中概念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，为测试数据的总长度。. 源程序：插入排序核心代码void InsertSort(int a,int p) int i,j,temp; for(i=1;i0&aj-1temp;j-) aj=aj-
24、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; for (i=0;ii;j-) /*比较,找出本趟最小关键字的记录*/ if (ajaj-1) temp=aj; /*进行互换,将最小关键字记录前移*/ aj=aj-1; aj-1
25、=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(int a,int n,int p) int i,j,low,high,temp,top=-1; struct node int low,high; stN; top+; sttop
26、.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+;sttop.low=low;sttop.high=i-1; top+;sttop.low=i+1;sttop.high=high; 时刻部份代码double TInsertSort(int a
27、,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_INTEGER liPerfNow=0; QueryPerformanceCounter(&liPerfNow); double time= - ; time/=;if(p!=6)Disp
28、(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 TSelectSort(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_liPerfStar
29、t=0; QueryPerformanceCounter(&m_liPerfStart);SelectSort(b,p);if(p!=6)Disp(b);getchar();LARGE_INTEGER liPerfNow=0; QueryPerformanceCounter(&liPerfNow); double time= - ; time/=;printf(n用直接选择排序法用的时刻为%f秒；,time);FILE *fp; fp=fopen(直接选择排序.txt,w);for(i=0;iN;i+) fprintf(fp,%d ,bi);fclose(fp);return(time);do
30、uble TBubbleSort(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);BubbleSort(b,p);LARGE_INTEGER liPerfNow=0; QueryPerformanceCounter(&liPerfNow); double time= - ;
31、 time/=;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 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_
32、INTEGER m_liPerfStart=0; QueryPerformanceCounter(&m_liPerfStart);heapsort(b,N,p);LARGE_INTEGER liPerfNow=0; QueryPerformanceCounter(&liPerfNow); double time= - ; time/=;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);r
33、eturn(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 liPerfNow=0; QueryPerformanceCounter(&liPerf
34、Now); double time= - ; time/=;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(double a) int i,j; double temp; for(i=1;i=i;j-) if(aj+1aj) temp=aj+1; aj+1=aj; aj=temp; 主界面代码void menu()printf( * 欢迎来到综合排序系统! *n); printf( n); printf( n);printf( n); printf( n);printf( n);printf( n);printf(
