（時間管理）語言各種排序方法及其所耗時間比較程序

1、（時間管理）語言各種排序方法及其所耗時間比較程序7 / 7#include<iostream.h>#include<stdlib.h>#include<iomanip.h>#include<time.h>#include<stdio.h>constintN=1000;/數(shù)據(jù)量,用于檢測算法質(zhì)量constintM=1000;/執(zhí)行次數(shù)/ 冒 泡 排 序 （ 遞 增 ） voidBubblesort(intr,intn)intflag=1;/flag 為 0 停止排序for(inti=1;i<n;i+)flag=0;for(intj

2、=n-1;j>=i;j-)if(rj<rj-1)intt=rj; rj=rj-1; rj-1=t; flag=1;if(flag=0) return;/快速排序voidquicksort(intr,intleft,intright)inti,j; intswap; i=left;j=right; swap=rleft; while(i<j)while(i<j)&&(swap<rj)j-; if(i<j)ri=rj; i+;while(i<j)&&(swap>ri)i+; if(i<j)rj=ri; j-;ri

3、=swap; if(i>left)quicksort(r,left,i-1); if(i<right) quicksort(r,i+1,right); return;/堆排序先建立堆voidcreatheap(intr,inti,intn)intj; intt;t=ri;j=2*i; while(j<n)if(j<n)&&(rj<rj+1)j+; if(t<rj)ri=rj; i=j;j=2*i;elsej=n; ri=t;/堆排序voidheapsort(intr,intn)intt; for(inti=n/2;i>=0;i-) cr

4、eatheap(r,i,n); for(i=n-1;i>=0;i-) t=r0;r0=ri; ri=t;creatheap(r,0,i-1);return;/二路歸且voidmerge(intr,intr1,intlow,intmid,inthigh)/進行二合壹的函數(shù)inti=low,j=mid+1,k=low; while(i<=mid)&&(j<=high)if(ri<=rj)r1k+=ri+;else r1k+=rj+;while(i<=mid) r1k+=ri+;while(j<=high) r1k+=rj+;voidmergepa

5、ss(intr,intr1,intlength)/用來區(qū)分填入 merge 函數(shù)的變量計算式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-1<N-1) merge(r,r1,i,i+length-1,N-1); elsefor(j=i;j<N;j+) r1j=rj;voidmergesort(intr)/二路且歸總算法intlength=1; intr1N+1; while(length<N)mergepass(r,r1,leng

6、th); length=2*length; mergepass(r1,r,length); length=2*length;return;/進行輸ftvoidprint(intr,intn)for(inti=0;i<=n-1;i+)if(i%10=0)cout<<endl; cout<<ri<<setw(6);cout<<endl;/主函數(shù)voidmain()inti,j,k; intrN,aN; clock_tstart,finish; doubleduration;cout<<"請選擇排序方式,1、冒泡法；2、快速

7、排序法；3、堆排序法；4、二路且歸法"<<endl; cin>>j;srand(unsigned)time(NULL); for(i=0;i<N;i+)ai=rand()%10000;switch(j)case(1):cout<<"冒泡法" start=clock(); for(i=0;i<M;i+)k=N-1;while(k+1)rk=ak; k-;Bubblesort(r,N);/冒泡法finish=clock(); duration=(double)(finish-start)/1000; print(r,N)

8、; printf("%fsecondsn",duration);break;case(2):cout<<"快速排序法" start=clock(); for(i=0;i<M;i+)k=N-1;while(k+1)rk=ak; k-;quicksort(r,0,N-1);/快速排序法finish=clock(); duration=(double)(finish-start)/1000; print(r,N); printf("%fsecondsn",duration);break; case(3):cout<&

9、lt;"堆排序法" start=clock(); for(i=0;i<M;i+)k=N-1;while(k+1)rk=ak; k-;heapsort(r,N);/堆排序法finish=clock(); duration=(double)(finish-start)/1000; print(r,N); printf("%fsecondsn",duration);break; case(4):cout<<"二路且歸法" start=clock(); for(i=0;i<M;i+)k=N-1;while(k+1)rk=ak