归并与快速排序算法对处理同等规模的数据的对比

浏览数：24 / 时间：2015年06月08日

用长分别为100、200、300、400、500、600、700、800、900、1000的10个数组的排列来统计这两种算法的时间复杂性；

快速排序程序：

#include<iostream>
using namespace std;

int circle;
static int num[11]={0,0,0,0,0,0,0,0,0,0,0};

void vector_initial(int *array,int n);
void vector_print(int *array,int n);
void fast_sort(int *array,int p,int r);
int separate_2part(int *array,int p,int r);
void count();

int main()
{
	int a[1000];
	int n;
	//cout<<"输入数的个数：";
	//cin>>n;
	for(circle=1;circle<=10;circle++)
	{
		vector_initial(a,circle);
		fast_sort(a,0,100*circle-1);
		vector_print(a,100*circle);
	}
	for(int i=1;i<=10;i++)
		cout<<i*100<<"个数据，执行步骤:"<<num[i]<<endl;
	return 0;
}

void vector_initial(int *array,int n)
{	int i=0;
	while(i<n*100)
	{
		array[i]=rand()%1000;
		i++;
	}
}
void vector_print(int *array,int n)
{
	for(int i=0;i<n;i++)
		cout<<array[i]<<" ";
	cout<<endl<<endl;
}

void fast_sort(int *array,int p,int r)
{
	int q;
	if(p<r)
	{
		q=separate_2part(array,p,r);
		fast_sort(array,p,q-1);
		fast_sort(array,q+1,r);
	}
}

int separate_2part(int *array,int p,int r)
{	
	int n1,n2,x;
	n1=p;
	n2=r;
	x=array[p];
	while(1)
	{
		while(array[++n1]<x)
		{
			 count();
		}
		while(array[n2]>x)
		{
			count();
			n2--;
		}
		if(n1>=n2) break;
		swap(array[n1],array[n2]);		
	}
	for(int i=p+1;i<=n2;i++)
	{
		array[i-1]=array[i];
	}
	array[n2]=x;
	return n2;
}

void count()
{
	switch(circle)
		{
		case 1:
				num[1]++;
				break;
		case 2:
				 num[2]++;
				 break;
		case 3:
				 num[3]++;
				 break;
		case 4:
				 num[4]++;
				 break;
		case 5:
				 num[5]++;
				 break;
		case 6:
				 num[6]++;
				 break;
		case 7:
				 num[7]++;
				 break;
		case 8:
				 num[8]++;
				 break;
		case 9:
				 num[9]++;
				 break;
		case 10:	 
				 num[10]++;
				 break;
		default:
			break;
		}

}

　　归并测试：

#include<iostream>
#include<time.h>
using namespace std;
int a[1000];
int circle;
static int num[11]={0,0,0,0,0,0,0,0,0,0,0};

void vector_initial(int n);
void print_vector(int circle);
void MERGE_sort(int p,int r);
void MERGE_combine(int p,int q,int r);

int main()
{	
	for(circle=1;circle<=10;circle++)
	{
		vector_initial(circle);
		MERGE_sort(0,circle*100-1);
		print_vector(circle*100);
	}
	for(int i=1;i<=10;i++)
		cout<<i*100<<"个数据，执行步骤:"<<num[i]<<endl;
	return 0;
}

void vector_initial(int n)
{	
	int i=0;
	while(i<n*100)
	{
		a[i]=rand()%1000;
		i++;
	}
}
void print_vector(int n)
{
	for(int i=0;i<n;i++)
	{
		cout<<a[i]<<" ";
		//if(19==i%20)
		//	cout<<endl;
	}
	cout<<endl<<endl<<endl;
}
void MERGE_sort(int p,int r)//归并排序
{	int q;
	if(p<r)
	{
		q=(p+r)/2;
		MERGE_sort(p,q);
		MERGE_sort(q+1,r);
		MERGE_combine(p,q,r);
	}
}

void MERGE_combine(int p,int q,int r)
{	
	int L[1000];
	int R[1000];
	int n1=q-p+1;
	int n2=r-q;
	for(int i=1;i<=n1;i++)
		L[i]=a[p+i-1];
	for(int j=1;j<=n2;j++)
		R[j]=a[q+j];
	L[n1+1]=100000;
	R[n2+1]=100000;
	i=1;j=1;
	for (int k=p;k<=r;k++)
	{
		switch(circle)
		{
		case 1:
				num[1]++;
				break;
		case 2:
				 num[2]++;
				 break;
		case 3:
				 num[3]++;
				 break;
		case 4:
				 num[4]++;
				 break;
		case 5:
				 num[5]++;
				 break;
		case 6:
				 num[6]++;
				 break;
		case 7:
				 num[7]++;
				 break;
		case 8:
				 num[8]++;
				 break;
		case 9:
				 num[9]++;
				 break;
		case 10:	 
				 num[10]++;
				 break;
		default:
			break;
		}
		if(L[i]<=R[j])
		{
			a[k]=L[i];
			i++;
		}
		else
		{
			a[k]=R[j];
			j++;
		}
	}
}

　　测试结果对比：

归并算法