各种排序算法性能比较

课程设计的目的(1)熟练使用C语言编写程序，解决实际问题;(2)了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力;(3)初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法

和技能;(4)提高综合运用所学的理论知识和方法独立分析和解决问题的能力;2需求分析（1）使用数组来存放产生的40000个随机数（2）编写统计程序运行时间的函数（3）编写快速排序、冒泡排序、插入排序、梳排序四种排序算法的函数(4)编写主函数，控制程序运行3课程设计报告内容3.1概要设计（1）使用四种排序算法：插入排序、冒泡排序、快速排序、梳排序（2）使用clock()函数来统计时间3.2详细设计主函数：intmain(){ intnumber[MAX]={0}; intnumber1[MAX]={0}; intnumber2[MAX]={0}; intnumber3[MAX]={0}; intnumber4[MAX]={0};inti;srand((unsigned)time(NULL));/*播种子*/for(i=0;i<MAX;i++) { number[i]=rand()%20000;/*产生101以内的随机整数*/number1[i]=number2[i]=number3[i]=number4[i]=number[i];while(number[i]==0) { number[i]=rand()%20000; number1[i]=number2[i]=number3[i]=number4[i]=number[i]; } }//快速排序并计算时间 clock_tbegin1,end1;doublecost1;begin1=clock(); quicksort(number1,MAX); end1=clock(); cost1=(double)(end1-begin1)/CLOCKS_PER_SEC;//冒泡排序并计算时间 clock_tbegin2,end2;doublecost2;begin2=clock(); Bubble(number2,MAX); end2=clock(); cost2=(double)(end2-begin2)/CLOCKS_PER_SEC; //插入排序并计算时间 clock_tbegin3,end3;doublecost3;begin3=clock(); insertSort(number3,MAX); end3=clock(); cost3=(double)(end3-begin3)/CLOCKS_PER_SEC; //梳排序并计算时间 clock_tbegin4,end4;doublecost4;begin4=clock(); combsort(number4,MAX); end4=clock(); cost4=(double)(end4-begin4)/CLOCKS_PER_SEC;for(intj=0;j<MAX;j++) { printf("%d",number1[j]); }printf("\n");printf("排序完成!\n");printf("快速排序耗时:%lfseconds\n",cost1);printf("冒泡排序耗时:%lfseconds\n",cost2);printf("插入排序耗时:%lfseconds\n",cost3);printf("梳排序耗时:%lfseconds\n",cost4); return0;}插入排序函数：voidinsertSort(inta[],intlen){ inti,j,temp; for(i=1;i<len;i++) { temp=a[i]; for(j=i-1;j>=0;j--) { if(a[j]>temp) { a[j+1]=a[j]; }else { break; } } a[j+1]=temp; }}冒泡排序函数：voidBubble(inta[],intlen){ intlength=len;inti=0;intj=0;for(;i<len;i++) { for(;j<length;j++) { if(a[j]>a[j+1]) { inttemp=a[j];a[j]=a[j+1];a[j+1]=temp; } }length--;j=0; }}快速排序函数：intpartions(intl[],intlow,inthigh){ intprvotkey=l[low];l[0]=l[low];while(low<high) { while(low<high&&l[high]>=prvotkey) --high;l[low]=l[high];while(low<high&&l[low]<=prvotkey) ++low;l[high]=l[low]; }l[low]=l[0];returnlow;}voidqsort(intl[],intlow,inthigh){ intprvotloc;if(low<high) { prvotloc=partions(l,low,high);//将第一次排序的结果作为枢轴qsort(l,low,prvotloc-1);//递归调用排序由low到prvotloc-1qsort(l,prvotloc+1,high);//递归调用排序由prvotloc+1到high }}voidquicksort(intl[],intn){ qsort(l,1,n);//第一个作为枢轴，从第一个排到第n个}梳排序函数：voidcombsort(inta[],intn){ floatshrink_factor=1.3;intgap=n,swapped=1,swap,i;while((gap>1)||swapped) { if(gap>1)gap=gap/shrink_factor;swapped=0;i=0;while((gap+i)<n) { if(a[i]-a[i+gap]>0) { swap=a[i];a[i]=a[i+gap];a[i+gap]=swap;swapped=1; }++i; } }}3.3调试分析（1）使用随机数产生函数，产生40000个随机数，再使用四种算法进行排序，并统计各种算法统计时间。（2）运行截图如下：（3）由多次试验结果可得，梳排序和快速排序的排序速度相对较快。4总结通过这次课程设计我主要熟悉了快速排序、冒泡排序、插入排序、梳排序四种排序算法的具体实现方法。我认识到了排序功能在解决实际问题中的作用，使我对数据结构的学习有了更进一步的理解。在完成本次课程设计中，我发现很多理论性知识在实际使用时与单纯的理论还是有所差别的，今后我会更加注重培养自己的实践动手能力。5程序清单见附录6参考文献[1]严蔚敏，吴伟民编著.数据结构(C语言版)--北京:清华大学出版社，2007.[2]严蔚敏，吴伟民米宁编著.数据结构题集(C语言版)--北京:清华大学出版社，2007.[3]/wiki/%E6%A2%B3%E6%8E%92%E5%BA%8F7程序运行结果附录程序清单：#include"stdafx.h"#include<stdio.h>#include<stdlib.h>#include<time.h>/*用到了time函数，所以要有这个头文件*/#defineMAX40000//插入排序voidinsertSort(inta[],intlen){ inti,j,temp; for(i=1;i<len;i++) { temp=a[i]; for(j=i-1;j>=0;j--) { if(a[j]>temp) { a[j+1]=a[j]; }else { break; } } a[j+1]=temp; }}//冒泡排序voidBubble(inta[],intlen){ intlength=len;inti=0;intj=0;for(;i<len;i++) { for(;j<length;j++) { if(a[j]>a[j+1]) { inttemp=a[j];a[j]=a[j+1];a[j+1]=temp; } }length--;j=0; }}//快速排序intpartions(intl[],intlow,inthigh){ intprvotkey=l[low];l[0]=l[low];while(low<high) { while(low<high&&l[high]>=prvotkey) --high;l[low]=l[high];while(low<high&&l[low]<=prvotkey) ++low;l[high]=l[low]; }l[low]=l[0];returnlow;}voidqsort(intl[],intlow,inthigh){ intprvotloc;if(low<high) { prvotloc=partions(l,low,high);//将第一次排序的结果作为枢轴qsort(l,low,prvotloc-1);//递归调用排序由low到prvotloc-1qsort(l,prvotloc+1,high);//递归调用排序由prvotloc+1到high }}voidquicksort(intl[],intn){ qsort(l,1,n);//第一个作为枢轴，从第一个排到第n个}//梳排序voidcombsort(inta[],intn){ floatshrink_factor=1.3;intgap=n,swapped=1,swap,i;while((gap>1)||swapped) { if(gap>1)gap=gap/shrink_factor;swapped=0;i=0;while((gap+i)<n) { if(a[i]-a[i+gap]>0) { swap=a[i];a[i]=a[i+gap];a[i+gap]=swap;swapped=1; }++i; } }}intmain(){ intnumber[MAX]={0}; intnumber1[MAX]={0}; intnumber2[MAX]={0}; intnumber3[MAX]={0}; intnumber4[MAX]={0};inti;srand((unsigned)time(NULL));/*播种子*/for(i=0;i<MAX;i++) { number[i]=rand()%20000;/*产生101以内的随机整数*/number1[i]=number2[i]=number3[i]=number4[i]=number[i];while(number[i]==0) { number[i]=rand()%20000; number1[i]=number2[i]=number3[i]=number4[i]=number[i]; } }//快速排序并计算时间 clock_tbegin1,end1;doublecost1;begin1=clock(); quicksort(number1,MAX); end1=clock(); cost1=(double)(end1-begin1)/CLOCKS_PER_SEC;//冒泡排序并计算时间 clock_tbegin2,end2;doublecost2;begin2=clock(); Bubble(number2,MAX); end2=cloc