#include<iostream.h>
int count1=0;
int count2=0;
template<class T>
void QuickSort(T *a,int n)
{//對(duì)進(jì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,//從左至右的游標(biāo)
		j=r+1;//從右到左的游標(biāo)
	T pivot=a[l];
	//把左側(cè)>=pivot的元素與右側(cè)<=pivot的元素進(jìn)行交換
	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)
{//使用歸并排序算法對(duì)a[0:n-1]進(jìn)行排序
	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){
		//歸并兩個(gè)大小為s的相鄰段
		Merge(x,y,i,i+s-1,i+2*s-1);
		i=i+2*s;
	}
//剩下不足兩個(gè)元素
	if(i+s<n)Merge(x,y,i,i+s-1,n-1);
	else for(int j=i;j<=n-1;j++)
         //把最后一段復(fù)制到y(tǒng)
		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,//第一段的游標(biāo)
j=m+1,//第二段的游標(biāo)
k=l;//結(jié)果的游標(biāo)
//只要在段中存在i和j，則不斷進(jìn)行歸并
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<<"請(qǐng)輸入需要比較數(shù)據(jù)的規(guī)模"<<endl;
    cin>>h;
	int *a=new int[h];
	int *b=new int[h];
	int *c=new int[h];
	cout<<"請(qǐng)按組輸入需要進(jìn)行排序的數(shù)據(jù)"<<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<<"規(guī)模是：          ";
	for(int k=1;k<=h;k++)
	cout<<k<<"    ";
	cout<<endl;
	cout<<"快排比較次數(shù)是：  ";
	cout<<b[0]<<"    ";
	for(k=2;k<=h;k++)
	cout<<b[k-1]-b[k-2]<<"    ";
	cout<<endl;
	cout<<"歸并排序比較次數(shù)是";
    cout<<c[0]<<"    ";
    for(k=2;k<=h;k++)
	cout<<c[k-1]-c[k-2]<<"    ";
	
}