八种排序算法效率比较
Terence发表于 2010-04-10 06:51:37
从刚上大一那会儿学的C语言开始，就已经接触到了不少排序算法，但当时都只是为了完成简单的排序任务而已，而且所给的数据也不够多，所以看不出各个排序算法间的执行效率的优劣。最近有个数据结构课程设计的实验，是有关于排序算法之间的效率比较，我就顺便把它放上来了，并对各个算法执行的效率时间做了柱形统计图表。此次实验主要测试了8种排序算法：插入排序、快速排序、冒泡排序、希尔排序、简单选择排序、堆排序、归并排序、折半插入排序。
总共建立了三种情况，分别是平均排序、最好情况排序、最坏情况排序。第一种情况就是使用了VC6.0下的随机数生成函数输出100000个随机数进行排序；第二种情况是100000个数本身已经按从小到大的顺序排列了；第三种情况就是100000个数全部是按逆序排列。代码如下：
#include#include #include #include #define MAX 100000 void InsSort(int r[],int length) { int i,j; for (i=2;i<=length;i++) { r[0]=r[i]; j=i-1; while(r[0]<r[j]) { r[j+1]=r[j]; j=j-1; } r[j+1]=r[0]; } } //插入排序 void swap(int &x,int &y) { int z; z=x; x=y; y=z; } int median3(int a[],int left,int right) { int center=(left+right)/2; if(a[left]>a[center]) swap(a[left],a[center]); if(a[left]>a[right]) swap(a[left],a[right]); if(a[center]>a[right]) swap(a[center],a[right]); swap(a[center],a[right-1]); return a[right-1]; } void insertionsort(int a[],int n) { int j,p; int tmp; for(p=1;p<=n;p++) { tmp=a[p]; for(j=p;j>0&&a[j-1]>tmp;j--) a[j]=a[j-1]; a[j]=tmp; } } void qsort(int a[],int left,int right) { int i,j; int pivot; if(left+2<=right) { pivot=median3(a,left,right); i=left;j=right-1; for(;;) { while(a[++i]<pivot){} while(a[--j]>pivot){} if(i<j) swap(a[i],a[j]); else break; } swap(a[i],a[right-1]); qsort(a,left,i-1); qsort(a,i+1,right); } else insertionsort(a+left,right-left+1); } void quicksort(int a[],int n) { qsort(a,0,n-1); } //快速排序 void BubbleSort(int r[],int length) { int i,j,temp; for(j=length;j>0;j--) for(i=0;i<j-1;i++) if(r[i]>r[i+1]) { temp=r[i]; r[i]=r[i+1]; r[i+1]=temp; } } //冒泡排序 void ShellInsert(int r[],int length,int delta) { int i,j; for(i=1+delta;i<=length;i++) if(r[i]<r[i-delta]) { r[0]=r[i]; for(j=i-delta;j>0&&r[0]<r[j];j-=delta) r[j+delta]=r[j]; r[j+delta]=r[0]; } } void ShellSort(int r[], int length, int delt[], int n) { int i; for(i=0;i<=n-1;++i) ShellInsert(r,length,delt[i]); } //希尔排序 void SelectSort(int r[],int length) { int i,j,k; int n; int x; n=length; for (i=1;i<=n-1;++i) { k=i; for(j=i+1;j<=n;++j) if(r[j]<r[k]) k=j; if( k!=i) { x= r[i]; r[i]=r[k]; r[k]=x; } } } //简单选择排序 void sift(int r[],int k,int m) { int t; int i,j; int x; int finished; t= r[k]; x=r[k]; i=k; j=2*i; finished=FALSE; while(j<=m&&!finished) { if(j<m&&r[j]< r[j+1]) j=j+1; if(x>=r[j]) finished=TRUE; else { r[i]=r[j]; i=j; j=2*i; } } r[i] =t; } void crt_heap(int r[], int length) { int i,n; n=length; for (i=n/2;i>=1;--i) sift(r,i,n); } void HeapSort(int r[],int length) { int i,n; int b; crt_heap(r,length); n= length; for (i=n;i>=2;--i) { b=r[1]; r[1]=r[i]; r[i]=b; sift(r,1,i-1); } } //堆排序 void merge(int a[],int tmparray[],int lpos,int rpos,int rightend) { int i,leftend,numelements,tmppos; leftend=rpos-1; tmppos=lpos; numelements=rightend-lpos+1; while(lpos<=leftend && rpos<=rightend) if(a[lpos]<=a[rpos]) tmparray[tmppos++]=a[lpos++]; else tmparray[tmppos++]=a[rpos++]; while(lpos<=leftend) tmparray[tmppos++]=a[lpos++]; while(rpos<=rightend) tmparray[tmppos++]=a[rpos++]; for(i=0;i<numelements;i++,rightend--) a[rightend]=tmparray[rightend]; } void msort(int a[],int tmparray[],int left,int right) { int center; if(left<right) { center=(left+right)/2; msort(a,tmparray,left,center); msort(a,tmparray,center+1,right); merge(a,tmparray,left,center+1,right); } } void mergesort(int a[],int n) { int *tmparray; tmparray=(int*)malloc(n*sizeof(int)); if(tmparray!=NULL) { msort(a,tmparray,0,n-1); free(tmparray); } else printf("no space for tmp array!"); } //归并排序 void BInsertSort(int num[],int n) { int length=n; int low,high,i,j,m; for(i=2;i<=length;i++) { num[0]=num[i]; low=1; high=i-1; while(low<=high) { m=(low+high)/2; if(num[0]<num[m]) high=m-1; else low=m+1; } for(j=i-1;j>=high+1;j--) num[j+1]=num[j]; num[high+1]=num[0]; } } //折半插入排序 void main() { long dwStart,dwStop,runtime; int num[MAX],a[MAX],i,j; dwStart=GetTickCount(); srand((unsigned)time(NULL)); for(i=0;i<MAX;i++) num[i]=rand(); dwStop=GetTickCount(); runtime=dwStop-dwStart; printf("生成%d个随机数运行了%ldms\n\n",MAX,runtime); printf("********平均排序时间********\n"); for(i=0;i<MAX;i++) a[i]=num[i]; dwStart=GetTickCount(); InsSort(a,MAX); dwStop=GetTickCount(); runtime=dwStop-dwStart; printf("使用插入排序运行了%ldms\n",runtime); for(i=0;i<MAX;i++) a[i]=num[i]; dwStart=GetTickCount(); quicksort(a,MAX); dwStop=GetTickCount(); runtime=dwStop-dwStart; printf("使用快速排序运行了%ldms\n",runtime); for(i=0;i<MAX;i++) a[i]=num[i]; dwStart=GetTickCount(); BubbleSort(a,MAX); dwStop=GetTickCount(); runtime=dwStop-dwStart; printf("使用冒泡排序运行了%ldms\n",runtime); int delt[10]={100,80,60,40,20,10,5,3,2,1}; for(i=0;i<MAX;i++) a[i]=num[i]; dwStart=GetTickCount(); ShellSort(a,MAX,delt,10); dwStop=GetTickCount(); runtime=dwStop-dwStart; printf("使用希尔排序运行了%ldms\n",runtime); for(i=0;i<MAX;i++) a[i]=num[i]; dwStart=GetTickCount(); SelectSort(a,MAX); dwStop=GetTickCount(); runtime=dwStop-dwStart; printf("使用简单选择排序运行了%ldms\n",runtime); for(i=0;i<MAX;i++) a[i]=num[i]; dwStart=GetTickCount(); HeapSort(a,MAX); dwStop=GetTickCount(); runtime=dwStop-dwStart; printf("使用堆排序运行了%ldms\n",runtime); for(i=0;i<MAX;i++) a[i]=num[i]; dwStart=GetTickCount(); mergesort(a,MAX); dwStop=GetTickCount(); runtime=dwStop-dwStart; printf("使用归并排序运行了%ldms\n",runtime); for(i=0;i<MAX;i++) a[i]=num[i]; dwStart=GetTickCount(); BInsertSort(a,MAX); dwStop=GetTickCount(); runtime=dwStop-dwStart; printf("使用折半插入排序运行了%ldms\n",runtime); printf("****************************\n\n"); printf("******最好情况排序时间******\n"); for(i=0;i<MAX;i++) a[i]=i; dwStart=GetTickCount(); InsSort(a,MAX); dwStop=GetTickCount(); runtime=dwStop-dwStart; printf("使用插入排序运行了%ldms\n",runtime); for(i=0;i<MAX;i++) a[i]=i; dwStart=GetTickCount(); quicksort(a,MAX); dwStop=GetTickCount(); runtime=dwStop-dwStart; printf("使用快速排序运行了%ldms\n",runtime); for(i=0;i<MAX;i++) a[i]=i; dwStart=GetTickCount(); BubbleSort(a,MAX); dwStop=GetTickCount(); runtime=dwStop-dwStart; printf("使用冒泡排序运行了%ldms\n",runtime); for(i=0;i<MAX;i++) a[i]=i; dwStart=GetTickCount(); ShellSort(a,MAX,delt,10); dwStop=GetTickCount(); runtime=dwStop-dwStart; printf("使用希尔排序运行了%ldms\n",runtime); for(i=0;i<MAX;i++) a[i]=i; dwStart=GetTickCount(); SelectSort(a,MAX); dwStop=GetTickCount(); runtime=dwStop-dwStart; printf("使用简单选择排序运行了%ldms\n",runtime); for(i=0;i<MAX;i++) a[i]=i; dwStart=GetTickCount(); HeapSort(a,MAX); dwStop=GetTickCount(); runtime=dwStop-dwStart; printf("使用堆排序运行了%ldms\n",runtime); for(i=0;i<MAX;i++) a[i]=i; dwStart=GetTickCount(); mergesort(a,MAX); dwStop=GetTickCount(); runtime=dwStop-dwStart; printf("使用归并排序运行了%ldms\n",runtime); for(i=0;i<MAX;i++) a[i]=i; dwStart=GetTickCount(); BInsertSort(a,MAX); dwStop=GetTickCount(); runtime=dwStop-dwStart; printf("使用折半插入排序运行了%ldms\n",runtime); printf("****************************\n\n"); printf("******最坏情况排序时间******\n"); for(i=MAX-1,j=0;i<=0,j<MAX;i--,j++) a[j]=i; dwStart=GetTickCount(); InsSort(a,MAX); dwStop=GetTickCount(); runtime=dwStop-dwStart; printf("使用插入排序运行了%ldms\n",runtime); for(i=MAX-1,j=0;i<=0,j<MAX;i--,j++) a[j]=i; dwStart=GetTickCount(); quicksort(a,MAX); dwStop=GetTickCount(); runtime=dwStop-dwStart; printf("使用快速排序运行了%ldms\n",runtime); for(i=MAX-1,j=0;i<=0,j<MAX;i--,j++) a[j]=i; dwStart=GetTickCount(); BubbleSort(a,MAX); dwStop=GetTickCount(); runtime=dwStop-dwStart; printf("使用冒泡排序运行了%ldms\n",runtime); for(i=MAX-1,j=0;i<=0,j<MAX;i--,j++) a[j]=i; dwStart=GetTickCount(); ShellSort(a,MAX,delt,10); dwStop=GetTickCount(); runtime=dwStop-dwStart; printf("使用希尔排序运行了%ldms\n",runtime); for(i=MAX-1,j=0;i<=0,j<MAX;i--,j++) a[j]=i; dwStart=GetTickCount(); SelectSort(a,MAX); dwStop=GetTickCount(); runtime=dwStop-dwStart; printf("使用简单选择排序运行了%ldms\n",runtime); for(i=MAX-1,j=0;i<=0,j<MAX;i--,j++) a[j]=i; dwStart=GetTickCount(); HeapSort(a,MAX); dwStop=GetTickCount(); runtime=dwStop-dwStart; printf("使用堆排序运行了%ldms\n",runtime); for(i=MAX-1,j=0;i<=0,j<MAX;i--,j++) a[j]=i; dwStart=GetTickCount(); mergesort(a,MAX); dwStop=GetTickCount(); runtime=dwStop-dwStart; printf("使用归并排序运行了%ldms\n",runtime); for(i=MAX-1,j=0;i<=0,j<MAX;i--,j++) a[j]=i; dwStart=GetTickCount(); BInsertSort(a,MAX); dwStop=GetTickCount(); runtime=dwStop-dwStart; printf("使用折半插入排序运行了%ldms\n",runtime); printf("****************************\n"); printf("\n排序测试完成！"); getchar(); }
执行程序是个很漫长的过程，像对于冒泡排序之类的算法，十万个数的排序再好的机器也得算上半天，不过像快速排序之类的算法如果不给予足够多的数据的话，执行时间永远是0毫秒。所以为了测算精确和公平比较，时间长我就慢慢熬吧。。。以下是我用执行完后的结果做成的统计图表（ps：图表中的数据是我在学院机器上的结果，在自己电脑上时间肯定会少许多，就懒得再算一遍了，反正情况都一样~~）：
结果很明显，快速排序、堆排序、归并排序这三种执行效率最快，不过话说回来，冒泡排序的代码真的是最好写的！看来算法高效代码复杂与算法低下代码简单是个很辩证的关系啊！ 
» 转载请注明来源：Terence的窝 » 《八种排序算法效率比较》