c语言各种排序方法与所耗时间比较程序.doc

#include #include #include #include #include const int N=1000;/数据量，用于检测算法质量const int M=1000;/执行次数/冒泡排序（递增）void Bubblesort(int r,int n)int flag=1;/flag为0停止排序for(int i=1;i=i;j-)if(rjrj-1)int t=rj;rj=rj-1;rj-1=t;flag=1;if(flag=0)return;/快速排序void quicksort(int r,int left,int right) int i,j; int swap; i=left;j=right; swap=rleft; while(ij) while(ij)&(swaprj)j-; if(ij) ri=rj; i+; while(iri)i+; if(ileft) quicksort(r,left,i-1); if(iright) quicksort(r,i+1,right); return;/堆排序先建立堆void creatheap(int r,int i,int n)int j;int t;t=ri;j=2*i;while(jn)if(jn)&(rjrj+1)j+;if(t=0;i-)creatheap(r,i,n);for(i= n-1;i=0;i-)t=r0;r0=ri;ri=t;creatheap(r,0,i-1);return;/二路归并void merge(int r,int r1,int low,int mid,int high)/进行二合一的函数int i=low,j=mid+1,k=low; while(i=mid)&(j=high)if(ri=rj)r1k+=ri+;elser1k+=rj+;while(i=mid)r1k+=ri+;while(j=high)r1k+=rj+;void mergepass(int r,int r1,int length)/用来区分填入merge函数的变量计算式int i=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+)r1j=rj;void mergesort(int r)/二路并归总算法int length=1;int r1N+1;while(lengthN)mergepass(r,r1,length);length=2*length;mergepass(r1,r,length);length=2*length;return;/进行输出void print(int r,int n)for(int i=0;i=n-1;i+)if(i%10=0)coutendl;coutrisetw(6);coutendl;/主函数void main()int i,j,k;int rN,aN;clock_t start, finish;double duration;cout请选择排序方式,1、冒泡法；2、快速排序法；3、堆排序法；4、二路并归法j;srand(unsigned)time(NULL); for(i=0;iN;i+)ai=rand()%10000;switch(j)case(1):cout冒泡法;start = clock();for(i=0;iM;i+)k=N-1;while(k+1)rk=ak;k-; Bubblesort(r,N);/冒泡法finish = clock();duration = (double)(finish - start)/1000; print(r,N);printf( %f secondsn, duration );break;case(2):cout快速排序法;start = clock();for(i=0;iM;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( %f secondsn, duration );break;case(3): cout堆排序法;start = clock();for(i=0;iM;i+)k=N-1;while(k+1)rk=ak;k-;heapsort(r,N);/堆排序法finish = clock();duration = (double)(finish - start)/1000; print(r,N);printf( %f secondsn, duration );break;case(4): cout二路并归法;start = clock();for(i=0;iM;i+)k=N-1;while(k+1)rk=ak;k-;mergesort(r);/