各种排序算法性能比较-顾云康E01114300

数据结构课程设计报告PAGE5数据结构课程设计实验报告姓名：顾云康学号：E1114300指导老师：王爱平日期：2013.10.8目录1课程设计的目的 32需求分析 33课程设计报告内容 33.1概要设计 33.2详细设计 43.3调试分析 124总结 135程序清单 146参考文献 147程序运行结果 14附录 15 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个随机数，再使用四种算法进行排序，并统计各种算法统计时间。运行截图如下：（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=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_P