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

1、课 程 设 计 课程：数据结构 题目：排序算法比较 专业班级： 姓名： 学号： 设计时间： 指导教师：设计题目排序算法比较运行环境（软、硬件环境）操作系统windows运行环境vc6.0算法设计的思想大架构采用模块化编程的思想，将每个不同的功能分别写成不同的子程序，分别进行封装构成各个小的模块，最后将各个模块组合起来。在每个子程序的编写过程中特事特办面对不同的预想功能采取不同的数据结构不同的算法实现。总体算法思想为按功能分块，依照预想功能实现顺序拼装。具体思想请见流程图。流程图开始功能流程图请用户输入将要生成随机数的上下限，按照上下限生成30000个随机数并输出随机生成随机数并输出请用户选择想

2、要使用的排序方法计算其使用的排序时间并输出询问用户是否继续运行程序否是输出结束语句结束程序编写流程图开始定义全局变量a30000,aaaa3000,结构体数组aa30000用来存放随机数，choice，choice1编写各个子算法子函数，和时间选择函数，既菜单选择函数，部分需要声明的函数在头文件下声明。各模块依据功能流程图组装结束算法流程图开始局部变量l，h收集上下限，sjs（）将用户选择数值赋值于choice，将choice作为参数调用time（），用if语句判断选择将要调用的算法子函数main1（）menu（）choice1=1Choice1=2结束算法设计分析 程序总体采用模块化设计，程

3、序间通过传参和调用进行有机组合。这样的总体布局将将各个功能隔离开来，每个模块负责每个模块的功能，使得程序的布局简单明了。且子程序只有在被调用时才会运行大大节约系统资源减少了运算时间。同时由于功能的隔离使得程序的扩展性大大提高，无论程序将要任何改动时，都会方便很多。源代码#include<stdio.h>#include<time.h>#include<stdlib.h>int a30000;int choice;int choice1;struct xlxint key;int link; aa30000;int aaa300000;void main1()

4、;/*直接插入排序函数*/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>

5、;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<

6、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); q

7、uick_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) =

8、 *(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); /*剩下的数再

9、建堆*/ /*归并排序*/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;elseliststart.link=second;start=second;second=listsecond.link;if (first=-1) liststart.link=seco

10、nd;else liststart.link=first;return list30000.link;int rmerge(struct xlx list,int lower,int upper) /* 归并并返回已排序的结果数组的起始位置*/int middle;if(lower>=upper)return lower;elsemiddle=(lower+upper);return listmerge(list,rmerge(list,lower,middle), rmerge(list,middle+1,upper); /*时间计算函数*/void timer(int choice)

11、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)/10

12、00;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 sjs()int i=0,j,b,h,l;printf("请输入你所期望的将

13、要生成随机数的取值范围：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+)printf("%d ",ai); void

14、 main1()printf("nn请选择你所希望使用的排序方法：nn1。直接插入排序n2。冒泡排序n3。选择排序n4。快速排序n5。堆排序n6。归并排序n");scanf("%d",&choice);timer(choice);printf("nn排序完毕，请选择下一步您要完成的工作：nn1.返回选择另一种排序方法排序n2.退出n");scanf("%d",&choice1);menu(choice1);/*主函数*/void main()sjs();main1(); for (k=n-1; k&

15、gt;=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;elseliststar

16、t.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;elsemiddle=(lower+upper);return listmerge(list,rmerg

17、e(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_sor

18、t(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);pr