c语言各种排序方法及其所耗时间比较程序

1、#include<iostream.h>#include <stdlib.h>#include <iomanip.h>#include <time.h>#include <stdio.h>const int N=1000;/ const int M=1000;/数据量，用于检测算法质量执行次数/ 冒泡排序（递增）void Bubblesort(int r,int n)int flag=1;/flagfor(int i=1;i<n;i+)为 0 停止排序flag=0;for(int j=n-1;j>=i;j-)if(rj&l

2、t;rj-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(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=swap;if(i>left)quicksor

3、t(r,left,i-1);if(i<right)quicksort(r,i+1,right);return;/ 堆排序先建立堆void creatheap(int r,int i,int n)int j;int t;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;else j=n;ri=t;/ 堆排序void heapsort(int r,int n)int t;for(int i=n/2;i>=0;i-)creatheap(r,i,n);for(i= n-

4、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 l

5、ength)/用来区分填入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-1<N-1)merge(r,r1,i,i+length-1,N-1);elsefor(j=i;j<N;j+)r1j=rj;void mergesort(int r)/二路并归总算法int length=1;int r1N+1;while(length<N)mergepass(r,r1,length);length=2*length;m

6、ergepass(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)cout<<endl;cout<<ri<<setw(6);cout<<endl;/ 主函数void main()int i,j,k;int rN,aN;clock_t start, finish;double duration;cout<<" 请选择排序方式,1 、冒泡法；2、快速排序法； 3、堆排序法；4、二

7、路并归法 "<<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);printf( &

8、quot;%f secondsn", 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( "%f secondsn", 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( "%f secondsn", duration );break;case(4):cout<<"二路并归法 "start = clock();for(i=0;i<M;i+)k=N-1;while(k+1)rk=ak