数据结构课程设计各种排序算法比较 附带源代码.doc

课 程 设 计 课程：数据结构 题目：排序算法比较 专业班级： 姓名： 学号： 设计时间： 指导教师：设计题目排序算法比较运行环境（软、硬件环境）操作系统windows运行环境vc6.0算法设计的思想大架构采用模块化编程的思想，将每个不同的功能分别写成不同的子程序，分别进行封装构成各个小的模块，最后将各个模块组合起来。在每个子程序的编写过程中特事特办面对不同的预想功能采取不同的数据结构不同的算法实现。总体算法思想为按功能分块，依照预想功能实现顺序拼装。具体思想请见流程图。流程图开始功能流程图请用户输入将要生成随机数的上下限，按照上下限生成30000个随机数并输出随机生成随机数并输出请用户选择想要使用的排序方法计算其使用的排序时间并输出询问用户是否继续运行程序否是输出结束语句结束程序编写流程图开始定义全局变量a30000,aaaa3000,结构体数组aa30000用来存放随机数，choice，choice1编写各个子算法子函数，和时间选择函数，既菜单选择函数，部分需要声明的函数在头文件下声明。各模块依据功能流程图组装结束算法流程图开始局部变量l，h收集上下限，sjs（）将用户选择数值赋值于choice，将choice作为参数调用time（），用if语句判断选择将要调用的算法子函数main1（）menu（）choice1=1Choice1=2结束算法设计分析 程序总体采用模块化设计，程序间通过传参和调用进行有机组合。这样的总体布局将将各个功能隔离开来，每个模块负责每个模块的功能，使得程序的布局简单明了。且子程序只有在被调用时才会运行大大节约系统资源减少了运算时间。同时由于功能的隔离使得程序的扩展性大大提高，无论程序将要任何改动时，都会方便很多。源代码#include#include#includeint a30000;int choice;int choice1;struct xlxint key;int link; aa30000;int aaa300000;void main1();/*直接插入排序函数*/void direct(int a)printf(n现在使用直接插入排序法进行排序:n);int i,j,w; for(i=0;i=0;j-) if(aj=aj+1) w=aj; aj=aj+1; aj+1=w; /*冒泡排序函数*/void bubble_sort(int a) printf(n下面使用冒泡排序法进行排序:); int i,j,w; for(i=0;i30000;i+) for(j=0;jaj+1) w=aj; aj=aj+1; aj+1=w; /*选择排序*/void choices_sort(int a) printf(n现在使用选择排序法进行排序:n); int i,j,k,t; for(i=0;i30000;i+) k=i; for(j=i+1;jaj) k=j; t=ai; ai=ak; ak=t; /*快速排序*/ quick(int first,int end,int L) int left=first,right=end,key; key=Lfirst; while(leftright) while(left=key) right-; if(leftright) Lleft+=Lright; while(leftright)&(Lleft=key) left+; if(leftright)Lright-=Lleft; Lleft=key; return left; void quick_sort(int L,int first,int end) int split; if(firstend) split=quick(first,end,L); quick_sort(L,first,split-1); quick_sort(L,split+1,end); /*堆排序*/void sift(int *x, int n, int s) int t, k, j; t = *(x+s); /*暂存开始元素*/ k = s; /*开始元素下标*/ j = 2*k + 1; /*右子树元素下标*/ while (jn) if (jn-1 & *(x+j) *(x+j+1) /*判断是否满足堆的条件：满足就继续下一轮比较，否则调整。*/ j+; if (t=0; i-) sift(x,n,i); /*初始建堆*/ for (k=n-1; k=1; k-) t = *(x+0); /*堆顶放到最后*/ *(x+0) = *(x+k); *(x+k) = t; sift(x,k,0); /*剩下的数再建堆*/ /*归并排序*/int listmerge(struct xlx list,int first,int second)/*递归传递*/int start=30000;while(first!=-1&second!=-1)if(listfirst.key=upper)return lower;elsemiddle=(lower+upper);return listmerge(list,rmerge(list,lower,middle), rmerge(list,middle+1,upper); /*时间计算函数*/void timer(int choice)double t1,t2,t;int i;t1=(double) clock(); if(choice=1) direct(a);if(choice=2) bubble_sort(a);if(choice=3) choices_sort(a);if(choice=4) printf(n现在使用快速排序法进行排序:n); quick_sort(a,0,29999); if(choice=5) heap_sort(a,30000);if(choice=6) rmerge(aa,0,29999);t2=(double) clock();t=difftime(t2,t1)/1000;for(i=0;i30000;i+) printf(%d ,ai);printf(n排序结束您所用排序时间为：%f秒n,t);/*菜单函数*/void menu(int choice1) int i;if (choice1=1) for(i=0;i=30000;i+)ai=aaai;aai.key=aaai;main1();if (choice1=2)printf(谢谢使用，再见！);/*生成随机数函数*/void sjs()int i=0,j,b,h,l;printf(请输入你所期望的将要生成随机数的取值范围：n);printf(最小值（不能为负数）：);scanf(%d,&l);printf(最大值（无上限）：);scanf(%d,&h);srand( (int) time(0);for(j=0;i=l&b=h)ai=b;aai.key=b;aaai=b;i+;for(i=0;i=1; k-) t = *(x+0); /*堆顶放到最后*/ *(x+0) = *(x+k); *(x+k) = t; sift(x,k,0); /*剩下的数再建堆*/ /*归并排序*/int listmerge(struct xlx list,int first,int second)/*递归传递*/int start=30000;while(first!=-1&second!=-1)if(listfirst.key=upper)return lower;elsemiddle=(lower+upper);return listmerge(list,rmerge(list,lower,middle), rmerge(list,middle+1,upper); /*时间计算函数*/void time(int choice) double t1,t2,t;int i;t1=(double) clock(); if(choice=1) direct(a);if(choice=2) bubble_sort(a);if(choice=3) choices_sort(a);if(choice=4) printf(n现在使用快速排序法进行排序:n); quick_sort(a,0,29999); if(choice=5) heap_sort(a,30000);if(choice=6) rmerge(aa,0,29999);t2=(double) clock();t=difftime(t2,t1)/1000;for(i=0;i30000;i+) printf(%d ,ai);printf(n排序结束您所用排序时间为：%f秒n,t);/*菜单函数*/void menu(int choice1) int i;if (choice1=1) for(i=0;i=30000;i+)ai=aaai;aai.key=aaai;main1();if (choice1=2)printf(谢谢使用，再见！); void main1()printf(nn请选择你所希望使用的排序方法：nn1。直接插入排序n2。冒泡排序n3。选择排序n4。快速排序n5。堆排序n6。归并排序n);scanf(%d,&choice);time(choice);printf(nn排序完毕，请选择下一步您要完成的工作：nn1.返回选择另一种排序方法排序n2.退出n);scanf(%d,&choice1);menu(choice1);/*主函数*/void main()sjs();main1();运行结果分析生成30000个随机数选择使用排序算法直接排序排序所用时间冒泡排序所用时间选择排序所用时间快速排序所用时间 堆排序所用时间各排序排序时间分别为：直接排序：3.448秒冒泡排序：3.76秒选择排序：1.575秒快速排序：0.00秒堆排序：0.016秒归并排序：7.487秒（注：此处快速排序并非排序时间为0，而是时间很短在表示范围外，当实验数据扩大到一定数值后会有相应时间显示）通过数据不难看出6种排序方法处理一组相同数据时，快速排序处理速度最快堆排序次之，归并排序最慢。六课设心得整个程序前