八种排序算法效率比较

首页 > 开发技术 > 八种排序算法效率比较

八种排序算法效率比较

2010年4月10日 Terence 3,207 次阅读发表评论阅读评论

从刚上大一那会儿学的C语言开始，就已经接触到了不少排序算法，但当时都只是为了完成简单的排序任务而已，而且所给的数据也不够多，所以看不出各个排序算法间的执行效率的优劣。最近有个数据结构课程设计的实验，是有关于排序算法之间的效率比较，我就顺便把它放上来了，并对各个算法执行的效率时间做了柱形统计图表。此次实验主要测试了8种排序算法：插入排序、快速排序、冒泡排序、希尔排序、简单选择排序、堆排序、归并排序、折半插入排序。

总共建立了三种情况，分别是平均排序、最好情况排序、最坏情况排序。第一种情况就是使用了VC6.0下的随机数生成函数输出100000个随机数进行排序；第二种情况是100000个数本身已经按从小到大的顺序排列了；第三种情况就是100000个数全部是按逆序排列。代码如下：

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<windows.h>
#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：图表中的数据是我在学院机器上的结果，在自己电脑上时间肯定会少许多，就懒得再算一遍了，反正情况都一样~~）：