您好,欢迎访问三七文档
当前位置:首页 > 商业/管理/HR > 管理学资料 > c语言各种排序方法及其所耗时间比较程序
#includeiostream.h#includestdlib.h#includeiomanip.h#includetime.h#includestdio.hconstintN=1000;//数据量,用于检测算法质量constintM=1000;//执行次数//冒泡排序(递增)voidBubblesort(intr[],intn){intflag=1;//flag为0停止排序for(inti=1;in;i++){flag=0;for(intj=n-1;j=i;j--)if(r[j]r[j-1]){intt=r[j];r[j]=r[j-1];r[j-1]=t;flag=1;}if(flag==0)return;}}//快速排序voidquicksort(intr[],intleft,intright){inti,j;intswap;i=left;j=right;swap=r[left];while(ij){while((ij)&&(swapr[j]))j--;if(ij){r[i]=r[j];i++;}while((ij)&&(swapr[i]))i++;if(ij){r[j]=r[i];j--;}}r[i]=swap;if(ileft)quicksort(r,left,i-1);if(iright)quicksort(r,i+1,right);return;}//堆排序先建立堆voidcreatheap(intr[],inti,intn){intj;intt;t=r[i];j=2*i;while(jn){if((jn)&&(r[j]r[j+1]))j++;if(tr[j]){r[i]=r[j];i=j;j=2*i;}elsej=n;r[i]=t;}}//堆排序voidheapsort(intr[],intn){intt;for(inti=n/2;i=0;i--)creatheap(r,i,n);for(i=n-1;i=0;i--){t=r[0];r[0]=r[i];r[i]=t;creatheap(r,0,i-1);}return;}//二路归并voidmerge(intr[],intr1[],intlow,intmid,inthigh)//进行二合一的函数{inti=low,j=mid+1,k=low;while((i=mid)&&(j=high)){if(r[i]=r[j])r1[k++]=r[i++];elser1[k++]=r[j++];}while(i=mid)r1[k++]=r[i++];while(j=high)r1[k++]=r[j++];}voidmergepass(intr[],intr1[],intlength)//用来区分填入merge函数的变量计算式{inti=0,j;while(i+2*length=N){merge(r,r1,i,i+length-1,i+2*length-1);i=i+2*length;}if(i+length-1N-1)merge(r,r1,i,i+length-1,N-1);elsefor(j=i;jN;j++)r1[j]=r[j];}voidmergesort(intr[])//二路并归总算法{intlength=1;intr1[N+1];while(lengthN){mergepass(r,r1,length);length=2*length;mergepass(r1,r,length);length=2*length;}return;}//进行输出voidprint(intr[],intn){for(inti=0;i=n-1;i++){if(i%10==0){coutendl;}coutr[i]setw(6);}coutendl;}//主函数voidmain(){inti,j,k;intr[N],a[N];clock_tstart,finish;doubleduration;cout请选择排序方式,1、冒泡法;2、快速排序法;3、堆排序法;4、二路并归法endl;cinj;srand((unsigned)time(NULL));for(i=0;iN;i++){a[i]=rand()%10000;}switch(j){case(1):{cout冒泡法;start=clock();for(i=0;iM;i++){k=N-1;while(k+1){r[k]=a[k];k--;}Bubblesort(r,N);//冒泡法}finish=clock();duration=(double)(finish-start)/1000;print(r,N);printf(%fseconds\n,duration);}break;case(2):{cout快速排序法;start=clock();for(i=0;iM;i++){k=N-1;while(k+1){r[k]=a[k];k--;}quicksort(r,0,N-1);//快速排序法}finish=clock();duration=(double)(finish-start)/1000;print(r,N);printf(%fseconds\n,duration);}break;case(3):{cout堆排序法;start=clock();for(i=0;iM;i++){k=N-1;while(k+1){r[k]=a[k];k--;}heapsort(r,N);//堆排序法}finish=clock();duration=(double)(finish-start)/1000;print(r,N);printf(%fseconds\n,duration);}break;case(4):{cout二路并归法;start=clock();for(i=0;iM;i++){k=N-1;while(k+1){r[k]=a[k];k--;}mergesort(r);//二路并归法}finish=clock();duration=(double)(finish-start)/1000;print(r,N);printf(%fseconds\n,duration);}break;}}
本文标题:c语言各种排序方法及其所耗时间比较程序
链接地址:https://www.777doc.com/doc-722591 .html