各种排序算法的时间耗费比较

各种排序算法的时间耗费比较//源代码如下：#includeiostream#includetime.h#includestdlib.h#includewindows.h#includestdio.h#includealgorithm#defineN100000//此处宏定义的范围似乎不能超过100000，甚至连100001也会出错usingnamespacestd;voidShow(int*s,intn){for(inti=0;in;i++)couts[i];coutendl;}voidRandData(int*s,intn){inti;srand(time(NULL));for(i=0;in;i++)s[i]=rand()%n;//Show(s,n);}voidSwap(inti,intj,int*s){intt;t=s[i];s[i]=s[j];s[j]=t;}/////////////////////////////////////////////////////////////////////////QuickSortintPartition(int*s,intl,intr){intleft=l;//recordtheleftsideintright=r+1;//recordtherightsidedo//为什么这个地方要用do-while而不能用while{doleft++;while(s[l]s[left]);//usingthel'skeywordasthemainkeydoright--;while(s[l]s[right]);if(leftright)Swap(left,right,s);}while(leftright);Swap(l,right,s);returnright;}voidQuickSort(int*s,intl,intr,intn){if(lr){intmid=Partition(s,l,r);QuickSort(s,l,mid-1,n);QuickSort(s,mid+1,r,n);}if(r-l+1==n){coutQuickSort:;//Show(s,n);}}/////////////////////////////////////////////////////////////////////////SelectSortvoidSelectSort(int*s,intn){inti,j,k;for(i=0;in-1;i++){k=i;for(j=i+1;jn;j++)if(s[j]s[k])k=j;if(k!=i)Swap(k,i,s);}coutSelectSort:;//Show(s,n);//thislinecannotputwiththepriorline.....Example:coutSelectSort:Show(s,n);}/////////////////////////////////////////////////////////////////////////BubbleSortvoidBubbleSort(int*s,intn){inti,j;for(i=0;in-1;i++)//justn-1roundsofcomparisionfor(j=0;jn-i-1;j++)if(s[j]s[j+1])Swap(j,j+1,s);coutBubbleSort:;//Show(s,n);}/////////////////////////////////////////////////////////////////////////InsertSort-插入排序voidInsertSort(int*s,intn){inti,j;intkey;for(i=1;in;i++)//startwiththesecondkeyword{key=s[i];for(j=0;ji;j++)if(s[j]key)break;for(intk=i;kj;k--)//keepattentionaboutthemovingorders[k]=s[k-1];s[j]=key;//Show(s,n);}coutInsertSort:;}/////////////////////////////////////////////////////////////////////////MergeSortvoidMerge(int*s,intleft,intright,intmid,intn){inti=left;intj=mid+1;inttemp[N];intk=0;while(imid+1&&jright+1){//twowaysoftransferingkeywordstotempwhile(s[i]s[j]&&ij&&imid+1)//here(ij)isamust,oritshouldchangeto(if(s[i]s[j])...)temp[k++]=s[i++];if(s[i]=s[j])//temp[k++]=s[j++];}while(jright+1)temp[k++]=s[j++];while(imid+1)temp[k++]=s[i++];for(i=left,j=0;iright+1;i++,j++)s[i]=temp[j];}voidMergeSort(int*s,intleft,intright,intn){if(leftright){intmid=(left+right)/2;MergeSort(s,left,mid,n);MergeSort(s,mid+1,right,n);Merge(s,left,right,mid,n);}if(right-left+1==n){coutMergeSort:;//Show(s,n);}}///////////////////////////////////////////////////////////////////////voidTest(int*s){doublestart,end;intnumber=10000;while(number100001){coutnumber个数据:endl;RandData(s,number);start=clock();//记录系统现在的时间,需要的头文件是time.hQuickSort(s,0,number-1,number);end=clock();cout(end-start)/1000endl;//将两个时间做差后即可得到排序所用的时间RandData(s,number);start=clock();sort(&s[0],&s[number]);end=clock();coutsort:(end-start)/1000endl;RandData(s,number);start=clock();MergeSort(s,0,number-1,number);end=clock();cout(end-start)/1000endl;RandData(s,number);start=clock();InsertSort(s,number);end=clock();cout(end-start)/1000endl;RandData(s,number);start=clock();SelectSort(s,number);end=clock();cout(end-start)/1000endl;RandData(s,number);start=clock();BubbleSort(s,number);end=clock();cout(end-start)/1000endl;number+=10000;}}intmain(){ints[N];Test(s);return0;//system(pause);//whythefinalsaidthatpausenotfound}