数据结构课程设计各种排序算法比较.docx

数据结构课程设计各种排序算法比较课 程 设 计 课程：数据结构 题目：排序算法比较专业班级： 姓名： 学号： 设计时间： 指导教师： 一、 设计题目 排序算法比较 二、 运行环境 操作系统windows 运行环境vc6.0 三、 算法设计的思想 大架构采用模块化编程的思想，将每个不同的功能分别写成不同的子程序，分别进行封装构成各个小的模块，最后将各个模块组合起来。在每个子程序的编写过程中特事特办面对不同的预想功能采取不同的数据结构不同的算法实现。 总体算法思想为按功能分块，依照预想功能实现顺序拼装。 具体思想请见流程图。 四、 流程图 功能流程图 开始 请用户输入将要生成随随机生成随机数并输机数的上下限，按照上下出 个随机数限生成30000并输出 是 请用户选择想要使用的排序方法计算其使用的排序时间并输出 询问用户是否继续运行程序 否 输出结束语句 结束 程序编写流程图 开始 定义全局变量 a30000,aaaa3000,结构体数组aa30000用来存放随机数，choice，choice1 编写各个子算法子函数，和时间选择函数，既菜单选择函数，部分需要声明的函数在头文件下声明。 各模块依据功能流程图组装 结束 算法流程图 开始 局部变量l，h收集上下限，sjs main1 choice1=1 将用户选择数值赋值于choice，将choice作为参数调用time，用if语句判断选择将要调用的算法子函数 menu Choice1=2 结束 五、 算法设计分析 程序总体采用模块化设计，程序间通过传参和调用进行有机组合。这样的总体布局将将各个功能隔离开来，每个模块负责每个模块的功能，使得程序的布局简单明了。且子程序只有在被调用时才会运行大大节约系统资源减少了运算时间。同时由于功能的隔离使得程序的扩展性大大提高，无论程序将要任何改动时，都会方便很多。 六、 源代码 #include<stdio.h> #include<time.h> #include<stdlib.h> int a30000; int choice; int choice1; struct xlx int key; int link; aa30000; int aaa300000; void main1; /*直接插入排序函数*/ void direct(int a) printf("n现在使用直接插入排序法进行排序:n"); int i,j,w; for(i=0;i<30000;i+) for(j=i;j>=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;i<30000;i+) for(j=0;j<30000-i;j+) if(aj>aj+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;i<30000;i+) k=i; for(j=i+1;j<30000;j+) 序 if(ak>aj) k=j; t=ai; ai=ak; ak=t; /*/ quick(int first,int end,int L) int left=first,right=end,key; 快速排序 key=Lfirst; while(left<right) while(left<right)&&(Lright>=key) right-; if(left<right) Lleft+=Lright; while(left<right)&&(Lleft<=key) left+; if(left<right)Lright-=Lleft; Lleft=key; return left; void quick_sort(int L,int first,int end) int split; if(first<end) 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 (j<n) if (j<n-1 && *(x+j) < *(x+j+1) 满足堆的条件：满足就继续下一轮比较，否则调整。 j+; if (t<*(x+j) /*暂存开 /*开始 /*右子树 /*判断是否*/ /*调整*/ *(x+k) = *(x+j); k = j; /*调整后，开始元素也随之调整*/ j = 2*k + 1; else 需要调整了，已经是个堆了，退出循环。 break; *(x+k) = t; 元素放到它正确位置*/ void heap_sort(int *x, int n) int i, k, t; for (i=n/2-1; i>=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<=listsecond.key) liststart.link=first; first=listsecond.link; else liststart.link=second; start=second; second=listsecond.link; if (first=-1) liststart.link=second; else liststart.link=first; return list30000.link; int rmerge(struct xlx list,int lower,int upper) /* 归并并返回已排序的结果数组的起始位置*/ int middle; if(lower>=upper) return lower; else middle=(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;i<30000;i+) printf("%d ",ai); printf("n排序结束您所用排序时间为： /*菜*/ void menu(int choice1) int i; if (choice1=1) 秒n",t); 单函数%f 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<30000;j+) b=rand; if(b>=l&&b<=h) ai=b; aai.key=b; aaai=b; i+; for(i=0;i<30000;i+) void main1 printf("nn请选择你所希望使用的排序方法：nn1。直接插入排序n2。冒泡排序n3。选择排序n4。快速排序n5。堆排序n6。归并排序n"); scanf("%d",&choice); timer(choice); printf("%d ",ai); printf("nn排序完毕，请选择下一步您要完成的工作：nn1.返回选择另一种排序方法排序n2.退出n"); scanf("%d",&choice1); menu(choice1); /*主函*/ void main sjs; main1; 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<=listsecond.key) liststart.link=first; first=listsecond.link; else liststart.link=second; start=second; second=listsecond.link; if (first=-1) liststart.link=second; else liststart.link=first; return list30000.link; int rmerge(struct xlx list,int lower,int upper) /* 归并并返回已排序的结果数组的起始位置*/ int middle; if(lower>=upper) return lower; else middle=(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;i<30000;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秒 通过数据不难看出6种排序方法处理一组相同数据时，快速排序处理速度最快堆排序次之，归并排序最慢。 六课设心得 整个程序前前后后整整用了一个星期，每天只要有空闲时间就在翻书本，画流程图，写代码，反反复复一点一点。一个星期的编写让我进步不少，心得也不少，但是说实话让我认识最深的是四点，刻骨铭心： 1. 对于编程来说看书很重要，但实实在在的动手去编才是王道！ 2. 任何程序想要写起来不被自己搞晕，就一定要画流程图，省时省事！ 3. 编程一定养成良好的编程习惯，无论命名还是结构！ 4. 任何程序算法是灵魂，程序的好坏很大部分取决于算法，只是一组数的排序差别就如此之大，跟别说一个比排序负责多倍的排序！