bijiao.cpp

该程序对快速排序与归并排序比较次数进行比较

#include<iostream.h>
int count1=0;
int count2=0;
template<class T>
void QuickSort(T *a,int n)
{//对进行快速排序
	//要求必须有最大值
	quickSort(a,0,n-1);}
template<class T>
void Swap(T&x,T&y)
{T t;
 t=x;
 x=y;
 y=t;
}
template<class T>
void quickSort(T a[],int l,int r)
{//排序a[l:r],a[r+1]有大值
	if(l>=r)return;
	int i=l,//从左至右的游标
		j=r+1;//从右到左的游标
	T pivot=a[l];
	//把左侧>=pivot的元素与右侧<=pivot的元素进行交换
	while(true){
		do{//
			i=i+1;
		    count1++;
		}while(a[i]<pivot);
		
		do{
			j=j-1;
            count1++;
		}while(a[j]>pivot);
		if(i>=j)break;
		Swap(a[i],a[j]);
	}
a[l]=a[j];
a[j]=pivot;

quickSort(a,l,j-1);
quickSort(a,j+1,r);

}


template<class T>
void MergeSort(T a[],int n)
{//使用归并排序算法对a[0:n-1]进行排序
	T *b=new T[n];
	int s=1;//段的大小
	while(s<n){
		MergePass(a,b,s,n);//从a归并到b
		s+=s;
       	MergePass(b,a,s,n);//从b归并到a
		s+=s;
	}
	delete b;
}

template<class T>
void MergePass(T x[],T y[],int s,int n)
{//归并大小为s的相邻段
	int i=0;
	while(i<=n-2*s){
		//归并两个大小为s的相邻段
		Merge(x,y,i,i+s-1,i+2*s-1);
		i=i+2*s;
	}
//剩下不足两个元素
	if(i+s<n)Merge(x,y,i,i+s-1,n-1);
	else for(int j=i;j<=n-1;j++)
         //把最后一段复制到y
		y[j]=x[j];
}

template<class T>
void Merge(T c[],T d[],int l,int m,int r)
{//把c[l:m]和c[l:r]归并到d[l:r]
int i=l,//第一段的游标
j=m+1,//第二段的游标
k=l;//结果的游标
//只要在段中存在i和j，则不断进行归并
while((i<=m)&&(j<=r))
if(c[i]<=c[j])
{
	d[k++]=c[i++];
	count2++;
}
else {
	d[k++]=c[j++];
    count2++;
}
	//考虑余下的部分

if(i>m)for(int q=j;q<=r;q++)
d[k++]=c[q];
else for(int q=i;q<=m;q++)
d[k++]=c[q];
}

void main()
{   int h=0;
    cout<<"请输入需要比较数据的规模"<<endl;
    cin>>h;
	int *a=new int[h];
	int *b=new int[h];
	int *c=new int[h];
	cout<<"请按组输入需要进行排序的数据"<<endl;
	for(int i=1;i<=h;i++)
	{for(int j=0;j<i;j++)cin>>a[j];
	QuickSort(a,i);
	b[i-1]=count1;
	MergeSort(a,i);
	c[i-1]=count2;
	}
    cout<<"规模是：          ";
	for(int k=1;k<=h;k++)
	cout<<k<<"    ";
	cout<<endl;
	cout<<"快排比较次数是：  ";
	cout<<b[0]<<"    ";
	for(k=2;k<=h;k++)
	cout<<b[k-1]-b[k-2]<<"    ";
	cout<<endl;
	cout<<"归并排序比较次数是";
    cout<<c[0]<<"    ";
    for(k=2;k<=h;k++)
	cout<<c[k-1]-c[k-2]<<"    ";
	
}