sort.h

来自「算法分析和设计」· C头文件 代码 · 共 259 行

#include <iostream.h>
#include <stdlib.h> //srand(),rand()函数
#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记录比较次数，movNum记录移动次数
};


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<<"冒泡排序的比较次数："<<cpNum<<"，移动次数："<<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<<"堆排序的比较次数是："<<cpNum<<"，移动次数是："<<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<<"插入排序的比较次数是："<<cpNum<<"，移动次数是："<<movNum<<endl;
}



/*两个待归并的子序列均在数组A中，其中第一个子序列的下标范围从l到m，第二个子序列的下标范围从m+1到n。
  归并后得到的新的有序序列粗放在另一个辅助数组B中，下标从l到n。
*/
template <typename T>
void Merge(T A[],T B[],long l,long m,long n)
{
	long i=l;//字母l，指示第一个序列
	long j=m+1;//j指示第二个序列
	long k=l;//字母l，指示存放位置
	while(i<=m && j<=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]中若干个长度为k的有序子序列按从前向后的顺序两两归并到数组swap中
template <typename T>
void MergePass(T A[],long n,T swap[],long k)
{
	long l1=0,l2;  //l1,l2分别指示第1和第2个子序列的下界
	long u1,u2;    //u1,u2分别指示第1和第2个子序列的上届
	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)  //还剩下一个有序子表，将其复制到swap
	{
		for(;l1<n;l1++)
			swap[l1]=A[l1];
	}
}

/*二路归并时要做多趟归并，第一趟归并时令归并的字序列长度为k=1，
  以后每执行一趟归并并将k加倍。待排序的原始数据放在数组e中，辅助数组swap用来存放每趟归并的结果。
  在一趟归并结束下一趟归并开始之前，应把swap数组中的数据放回到数组e中。
 */
template <typename T>
void Sort<T>::MergeSort(T e[],long n)   //对e[0]到e[n-1]排序
{
	long k=1;//数字1  //k表示子表的长度
	T *swap=new T[n];  //动态申请辅助数组
	while(k<n)
	{
		MergePass(e,n,swap,k);
		for(long i=0;i<n;i++)  //将归并后的数据放回数组e
			e[i]=swap[i];
		k=2*k;   //归并长度加倍
	}
//	cout<<"归并排序的比较次数是："<<cpNum<<"，移动次数是："<<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) //对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) //对A[low]~A[high]排序
{
	double cpNum=0;
	double movNum=0;
	QuickSort1(A,low,high,cpNum,movNum);
	cout<<"快速排序的比较次数是："<<cpNum<<"，移动次数是："<<movNum<<endl;
}