#include <iostream.h>
#include <stdlib.h> //srand(),rand()函數(shù)
#include <stdio.h>
#include <time.h> //time()
//#include <windows.h>  //DWORD,   GetTickCount()

const long NUM=100000;

template <typename T>
class Sort
{
public:
	void BubbleSort(T e[],long n);                  //冒泡排序
	void HeapSort(T e[],long n);					   //堆排序
	void InsertSort(T e[],long n);                  //直接插入排序
	void MergeSort(T e[],long n);                   //歸并排序
	void QuickSort(T A[],long low,long high);        //快速排序
private:
//	T a[NUM];
//	double cpNum,movNum;  //cpNum記錄比較次數(shù)，movNum記錄移動(dòng)次數(shù)
};


template <typename T>
void Sort<T>::BubbleSort(T e[],long n)
{
	long lastExchangeIndex;
	T temp;
	long i=n-1;
	double cpNum=0;
	double movNum=0;
	while(i>0)
	{
		lastExchangeIndex=0;
		for(long j=0;j<i;j++)
		{
			cpNum++;
			if(e[j+1]<e[j])
			{
				movNum++;
				temp=e[j];
				e[j]=e[j+1];
				e[j+1]=temp;
				lastExchangeIndex=j;
			}
		}
		i=lastExchangeIndex;
	}
	cout<<"冒泡排序的比較次數(shù)："<<cpNum<<"，移動(dòng)次數(shù)："<<movNum<<endl;
}




template <typename T>
void FilterDown(T A[],long i,long n,double &c,double &m)
{
	long current=i;
	long j=2*i+1;
	T temp=A[i];
	while(j<n)
	{
		//非遞減順序排序
		c++;
		if(j<n-1 && A[j]<A[j+1])  //if(j<n-1 && A[j]>A[j+1])非遞增順序
			j++;
		c++;
		if(temp>=A[j])            //(temp<A[j])非遞增順序
			break;
		else
		{
			A[current]=A[j];
			m++;
			current=j;
			j=2*j+1;
		}
	}
	A[current]=temp;
}

template <typename T>
void Sort<T>::HeapSort(T e[],long n)
{
	double cpNum=0;
	double movNum=0;
	T temp;
	for(long i=(n-2)/2;i>=0;i--)
		FilterDown(e,i,n,cpNum,movNum);
	for(long j=n-1;j>=1;j--)
	{
		temp=e[j];
		e[j]=e[0];
		e[0]=temp;
		FilterDown(e,0,j,cpNum,movNum);
	}

	cout<<"堆排序的比較次數(shù)是："<<cpNum<<"，移動(dòng)次數(shù)是："<<movNum<<endl;
}



template <typename T>
void Sort<T>::InsertSort(T e[],long n)
{
	double cpNum=0,movNum=0;
	T temp;
	for(long i=1;i<n;i++)
	{
		temp=e[i];
		for(long j=i-1;(j>=0) && (temp<e[j]);j--)
		{
			cpNum++;
			e[j+1]=e[j];
			movNum++;
		}
		if(temp>e[j])
			cpNum++;
		e[j+1]=temp;
	}
	cout<<"插入排序的比較次數(shù)是："<<cpNum<<"，移動(dòng)次數(shù)是："<<movNum<<endl;
}



/*兩個(gè)待歸并的子序列均在數(shù)組A中，其中第一個(gè)子序列的下標(biāo)范圍從l到m，第二個(gè)子序列的下標(biāo)范圍從m+1到n。
  歸并后得到的新的有序序列粗放在另一個(gè)輔助數(shù)組B中，下標(biāo)從l到n。
*/
template <typename T>
void Merge(T A[],T B[],long l,long m,long n)
{
	long i=l;//字母l，指示第一個(gè)序列
	long j=m+1;//j指示第二個(gè)序列
	long k=l;//字母l，指示存放位置
	while(i<=m && j<=n)//當(dāng)兩個(gè)序列都未結(jié)束時(shí)循環(huán)
		if(A[i]<=A[j])
			B[k++]=A[i++];
		else
			B[k++]=A[j++];
	while(i<=m)
		B[k++]=A[i++];
	while(j<=n)
		B[k++]=A[j++];
}

//一趟歸并，將A[0]~A[n-1]中若干個(gè)長(zhǎng)度為k的有序子序列按從前向后的順序兩兩歸并到數(shù)組swap中
template <typename T>
void MergePass(T A[],long n,T swap[],long k)
{
	long l1=0,l2;  //l1,l2分別指示第1和第2個(gè)子序列的下界
	long u1,u2;    //u1,u2分別指示第1和第2個(gè)子序列的上屆
	while(l1+k<=n-1)
	{
		l2=l1+k;
		u1=l2-1;
		u2=(l2+k-1<=n-1)?l2+k-1:n-1;
		Merge(A,swap,l1,u1,u2);
		l1=u2+1;
	}
	if(l1<n)  //還剩下一個(gè)有序子表，將其復(fù)制到swap
	{
		for(;l1<n;l1++)
			swap[l1]=A[l1];
	}
}

/*二路歸并時(shí)要做多趟歸并，第一趟歸并時(shí)令歸并的字序列長(zhǎng)度為k=1，
  以后每執(zhí)行一趟歸并并將k加倍。待排序的原始數(shù)據(jù)放在數(shù)組e中，輔助數(shù)組swap用來存放每趟歸并的結(jié)果。
  在一趟歸并結(jié)束下一趟歸并開始之前，應(yīng)把swap數(shù)組中的數(shù)據(jù)放回到數(shù)組e中。
 */
template <typename T>
void Sort<T>::MergeSort(T e[],long n)   //對(duì)e[0]到e[n-1]排序
{
	long k=1;//數(shù)字1  //k表示子表的長(zhǎng)度
	T *swap=new T[n];  //動(dòng)態(tài)申請(qǐng)輔助數(shù)組
	while(k<n)
	{
		MergePass(e,n,swap,k);
		for(long i=0;i<n;i++)  //將歸并后的數(shù)據(jù)放回?cái)?shù)組e
			e[i]=swap[i];
		k=2*k;   //歸并長(zhǎng)度加倍
	}
//	cout<<"歸并排序的比較次數(shù)是："<<cpNum<<"，移動(dòng)次數(shù)是："<<movNum<<endl;
	delete []swap;
}





template <typename T>
void Swap(T &x,T &y)
{
	T temp=x;
	x=y;
	y=temp;
}

template <typename T>
void QuickSort1(T A[],long low,long high,double &c,double &m) //對(duì)A[low]~A[high]排序
{
	T pivot;
	long scanUp,scanDown;
	long mid;
	if(high-low<=0)
		return;
	else
	{
		if(high-low==1)
		{
			c++;
			if(A[high]<A[low])
			{
				m=m+3;
				Swap(A[low],A[high]);
			}
			return;
		}
	}
	mid=(low+high)/2;
	pivot=A[mid];
	Swap(A[mid],A[low]);
	m=m+3;
	scanUp=low+1;
	scanDown=high;
	do
	{
		while(scanUp<=scanDown && A[scanUp]<=pivot)
		{
			c++;
			scanUp++;
		}
		while(pivot<A[scanDown])
		{
			c++;
			scanDown--;
		}
		if(scanUp<scanDown)
		{
			m=m+3;
			Swap(A[scanUp],A[scanDown]);
		}
	}while(scanUp<scanDown);
	A[low]=A[scanDown];
	A[scanDown]=pivot;
	if(low<scanDown-1)
		QuickSort1(A,low,scanDown-1,c,m);
	if(scanDown+1<high)
		QuickSort1(A,scanDown+1,high,c,m);
}

template <typename T>
void Sort<T>::QuickSort(T A[],long low,long high) //對(duì)A[low]~A[high]排序
{
	double cpNum=0;
	double movNum=0;
	QuickSort1(A,low,high,cpNum,movNum);
	cout<<"快速排序的比較次數(shù)是："<<cpNum<<"，移動(dòng)次數(shù)是："<<movNum<<endl;
}