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

课程设计课程：数据结构题目：排序算法比较专业班级：姓名：学号：设计时间：指导教师：设计题目排序算法比较运行环境（软、硬件环境）操作系统windows运行环境vc6.0算法设计的思想大架构采用模块化编程的思想，将每个不同的功能分别写成不同的子程序，分别进行封装构成各个小的模块，最后将各个模块组合起来。在每个子程序的编写过程中特事特办面对不同的预想功能采取不同的数据结构不同的算法实现。总体算法思想为按功能分块，依照预想功能实现顺序拼装。具体思想请见流程图。流程图功能流程图开始程序编写流程图随机生成随机数并输出请用户选择想要使用的排序方法计算其使用的排序时间并输出询问用户是否继续运行程序否是输出结束语句结束请用户输入将要生成随机数的上下限，按照上下限生成30000个随机数并输出算法流程图开始定义全局变量a[30000],aaaa[3000],结构体数组aa[30000]用来存放随机数，choice，choice1编写各个子算法子函数，和时间选择函数，既菜单选择函数，部分需要声明的函数在头文件下声明。各模块依据功能流程图组装结束算法设计分析程序总体采用模块化设计，程序间通过传参和调用进行有机组合。这样的总体布局将将各个功能隔离开来，每个模块负责每个模块的功能，使得程序的布局简单明了。且子程序只有在局部变量l，h收集上下限，sjs（）将用户选择数值赋值于choice，将choice作为参数调用time（），用if语句判断选择将要调用的算法子函数main1（）menu（）choice1==1Choice1==2结束开始被调用时才会运行大大节约系统资源减少了运算时间。同时由于功能的隔离使得程序的扩展性大大提高，无论程序将要任何改动时，都会方便很多。源代码#includestdio.h#includetime.h#includestdlib.hinta[30000];intchoice;intchoice1;structxlx{intkey;intlink;}aa[30000];intaaa[300000];voidmain1();/*************************直接插入排序函数***********************/voiddirect(inta[]){printf(\n现在使用直接插入排序法进行排序:\n);inti,j,w;for(i=0;i30000;i++){for(j=i;j=0;j--){if(a[j]=a[j+1]){w=a[j];a[j]=a[j+1];a[j+1]=w;}}}}/*************************冒泡排序函数*************************/voidbubble_sort(inta[]){printf(\n下面使用冒泡排序法进行排序:);inti,j,w;for(i=0;i30000;i++)for(j=0;j30000-i;j++)if(a[j]a[j+1]){w=a[j];a[j]=a[j+1];a[j+1]=w;}}/*************************选择排序****************************/voidchoices_sort(inta[]){printf(\n现在使用选择排序法进行排序:\n);inti,j,k,t;for(i=0;i30000;i++){k=i;for(j=i+1;j30000;j++)if(a[k]a[j])k=j;t=a[i];a[i]=a[k];a[k]=t;}}/*************************快速排序****************************/quick(intfirst,intend,intL[]){intleft=first,right=end,key;key=L[first];while(leftright){while((leftright)&&(L[right]=key))right--;if(leftright)L[left++]=L[right];while((leftright)&&(L[left]=key))left++;if(leftright)L[right--]=L[left];}L[left]=key;returnleft;}voidquick_sort(intL[],intfirst,intend){intsplit;if(firstend){split=quick(first,end,L);quick_sort(L,first,split-1);quick_sort(L,split+1,end);}}/**************************堆排序*****************************/voidsift(int*x,intn,ints){intt,k,j;t=*(x+s);/*暂存开始元素*/k=s;/*开始元素下标*/j=2*k+1;/*右子树元素下标*/while(jn){if(jn-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;/*开始元素放到它正确位置*/}voidheap_sort(int*x,intn){inti,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);/*剩下的数再建堆*/}}/*************************归并排序****************************/intlistmerge(structxlxlist[],intfirst,intsecond)/*递归传递*/{intstart=30000;while(first!=-1&&second!=-1)if(list[first].key=list[second].key){list[start].link=first;first=list[second].link;}else{list[start].link=second;start=second;second=list[second].link;}if(first=-1)list[start].link=second;elselist[start].link=first;returnlist[30000].link;}intrmerge(structxlxlist[],intlower,intupper)/*归并并返回已排序的结果数组的起始位置*/{intmiddle;if(lower=upper)returnlower;else{middle=(lower+upper);returnlistmerge(list,rmerge(list,lower,middle),rmerge(list,middle+1,upper));}}/*************************时间计算函数************************/voidtimer(intchoice){doublet1,t2,t;inti;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,a[i]);printf(\n排序结束您所用排序时间为：%f秒\n,t);}/**************************菜单函数***************************/voidmenu(intchoice1){inti;if(choice1==1){for(i=0;i=30000;i++){a[i]=aaa[i];aa[i].key=aaa[i];}main1();}if(choice1==2){printf(谢谢使用，再见！！);}}/**************************生成随机数函数**********************/voidsjs(){inti=0,j,b,h,l;printf(请输入你所期望的将要生成随机数的取值范围：\n);printf(最小值（不能为负数）：);scanf(%d,&l);printf(最大值（无上限）：);scanf(%d,&h);srand((int)time(0));for(j=0;i30000;j++){b=rand();if(b=l&&b=h){a[i]=b;aa[i].key=b;aaa[i]=b;i++;}}for(i=0;i30000;i++)printf(%d,a[i]);}voidmain1(){printf(\n\n请选择你所希望使用的排序方法：\n\n1。直接插入排序\n2。冒泡排序\n3。选择排序\n4。快速排序\n5。堆排序\n6。归并排序\n);scanf(%d,&choice);timer(choice);printf(\n\n排序完毕，请选择下一步您要完成的工作：\n\n1.返回选择另一种排序方法排序\n2.退出\n);scanf(%d,&choice1);menu(choice1);}/*************************主函数******************************/voidmain(){sjs();main1();}for(k=n-1;k=1;k--){t=*(x+0);/*堆顶放到最后*/*(x+0)=*(x+k);*(x+k)=t;sift(x,k,0);/*剩下的数再建堆*/}}/*************************归并排序****************************/intlistmerge(structxlxlist[],intfirst,intsecond)/*递归传递*/{intstart=30000;while(first!=-1&&second!=-1)if(list[first].key=list[second].key){list[start].link=first;first=list[second].link;}else{list[start].link=second;start=second;second=list[second].link;}if(first=-1)list[start].link=second;elselist[start].link=first;returnlist[30000].link;}intrmerge(structxlxlist[],intlower,intupper)/*归并并返回已排序的结果数组的起始位置*/{intmiddle;if(lower=upper)returnlower;else{middle=(lower+upper);returnlistmerge(list,rmerge(list,lower,middle),r