各種排序算法性能比較-顧云康E01114300

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告PAGE5數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)實(shí)驗(yàn)報(bào)告姓名：顧云康學(xué)號(hào)：E1114300指導(dǎo)老師：王愛平日期：2013.10.8目錄1課程設(shè)計(jì)的目的 32需求分析 33課程設(shè)計(jì)報(bào)告內(nèi)容 33.1概要設(shè)計(jì) 33.2詳細(xì)設(shè)計(jì) 43.3調(diào)試分析 124總結(jié) 135程序清單 146參考文獻(xiàn) 147程序運(yùn)行結(jié)果 14附錄 15 clock_tbegin3,end3;doublecost3;begin3=clock(); insertSort(number3,MAX); end3=clock(); cost3=(double)(end3-begin3)/CLOCKS_PER_SEC; //梳排序并計(jì)算時(shí)間 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("快速排序耗時(shí):%lfseconds\n",cost1);printf("冒泡排序耗時(shí):%lfseconds\n",cost2);printf("插入排序耗時(shí):%lfseconds\n",cost3);printf("梳排序耗時(shí):%lfseconds\n",cost4); return0;}插入排序函數(shù)：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; }}冒泡排序函數(shù)：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; }}快速排序函數(shù)：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);//將第一次排序的結(jié)果作為樞軸qsort(l,low,prvotloc-1);//遞歸調(diào)用排序由low到prvotloc-1qsort(l,prvotloc+1,high);//遞歸調(diào)用排序由prvotloc+1到high }}voidquicksort(intl[],intn){ qsort(l,1,n);//第一個(gè)作為樞軸，從第一個(gè)排到第n個(gè)}梳排序函數(shù)：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調(diào)試分析（1）使用隨機(jī)數(shù)產(chǎn)生函數(shù)，產(chǎn)生40000個(gè)隨機(jī)數(shù)，再使用四種算法進(jìn)行排序，并統(tǒng)計(jì)各種算法統(tǒng)計(jì)時(shí)間。運(yùn)行截圖如下：（3）由多次試驗(yàn)結(jié)果可得，梳排序和快速排序的排序速度相對(duì)較快。4總結(jié)通過這次課程設(shè)計(jì)我認(rèn)識(shí)到了排序功能在解決實(shí)際問題中的作用，使我對(duì)數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)有了更進(jìn)一步的理解。在完成本次課程設(shè)計(jì)中，我發(fā)現(xiàn)很多理論性知識(shí)在實(shí)際使用時(shí)與單純的理論還是有所差別的，今后我會(huì)更加注重培養(yǎng)自己的實(shí)踐動(dòng)手能力。5程序清單見附錄6參考文獻(xiàn)[1]嚴(yán)蔚敏，吳偉民編著.數(shù)據(jù)結(jié)構(gòu)(C語言版)--北京:清華大學(xué)出版社，2007.[2]嚴(yán)蔚敏，吳偉民米寧編著.數(shù)據(jù)結(jié)構(gòu)題集(C語言版)--北京:清華大學(xué)出版社，2007.[3]/wiki/%E6%A2%B3%E6%8E%92%E5%BA%8F7程序運(yùn)行結(jié)果附錄程序清單：#include"stdafx.h"#include<stdio.h>#include<stdlib.h>#include<time.h>/*用到了time函數(shù)，所以要有這個(gè)頭文件*/#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);//將第一次排序的結(jié)果作為樞軸qsort(l,low,prvotloc-1);//遞歸調(diào)用排序由low到prvotloc-1qsort(l,prvotloc+1,high);//遞歸調(diào)用排序由prvotloc+1到high }}voidquicksort(intl[],intn){ qsort(l,1,n);//第一個(gè)作為樞軸，從第一個(gè)排到第n個(gè)}//梳排序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;/*產(chǎn)生101以內(nèi)的隨機(jī)整數(shù)*/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]; } }//快速排序并計(jì)算時(shí)間 clock_tbegin1,end1;doublecost1;begin1=clock(); quicksort(number1,MAX); end1=clock(); cost1=(double)(end1-begin1)/CLOCKS_PER_SEC;//冒泡排序并計(jì)算時(shí)間 clock_tbegin2,end2;doublecost2;begin2=clock(); Bubble(number2,MAX); end2=clock(); cost2=(double)(end2-begin2)/CLOCKS_PER_SEC; //插入排序并計(jì)算時(shí)間 clock_tbegin3,end3;doublecost3;begin3=clock(); insertSort(number3,MAX); end3=clock(); cost3=(double)(end3-begin3)/CLOCKS_PER_SEC; //梳排序并計(jì)算時(shí)間 clock_tbegin4,end4;doublecost4;begin4=clock(); combsort(number4,MAX); end4=clock(); cost4=(double)(end4-begin4)/CLOCKS_P