mergesort.h

各种排序算法BubbleSort、DichotomySort、HeapSort、InsertSort、MergeSort、QuickSort、ShellSort、

#ifndef MERGESORT_H
#define MERGESORT_H
#include<iostream.h>

template<class Elem>
class MergeSort:public sort<Elem>
{
	public:
		MergeSort(){compareNum = 0 ; moveNum = 0;};
		virtual void Sorts(Elem Array[] , Elem Temp[] , int left , int right);
		void print_m(Elem Array[] , int n);
		void Merge(Elem Array[] , Elem Temp[] , int left , int right , int middle);
	private:
		int compareNum;
		int moveNum;
};
template<class Elem>
void MergeSort<Elem>::Sorts(Elem Array[] , Elem Temp[] , int left , int right)
{
	if(left < right)
	{
		int middle = (left + right) / 2;
		Sorts(Array , Temp , left , middle);
		Sorts(Array , Temp , middle+1 , right);
		//Merge(Array , Temp , left , right , middle);
		for(int i = left ; i <= right ; i++)
			Temp[i] = Array[i];
		int index1 = left;//左边子序列的起始位置
		int index2 = middle+1;//右子序列起始位置
		int j = left;//从左开始归并
		while( (index1 <= middle) && (index2 <= right) )//(index1 < middle) && (index2 < right)
		{//取较小者插入合并数组中
			if( compare(Temp[index1],Temp[index2]) == -1 )
				Array[j++] = Temp[index1++];
			else
				Array[j++] = Temp[index2++];
			compareNum++;
			moveNum++;
		}
		while(index1 <= middle)
		{
			Array[j++] = Temp[index1++];
			compareNum++;
			moveNum++;
		}
		while(index2 <= right)
		{
			Array[j++] = Temp[index2++];
			compareNum++;
			moveNum++;
		}
	}
}
/*template<class Elem>
void MergeSort<Elem>::Merge(Elem Array[] , Elem Temp[] , int left , int right , int middle)
{
	for(int i = left ; i <= right ; i++)
		Temp[i] = Array[i];
	int index1 = left;//左边子序列的起始位置
	int index2 = middle+1;//右子序列起始位置
	int j = left;//从左开始归并
	while( (index1 <= middle) && (index2 <= right) )//(index1 < middle) && (index2 < right)
	{//取较小者插入合并数组中
		if( compare(Temp[index1],Temp[index2]) == -1 )
			Array[j++] = Temp[index1++];
		else
			Array[j++] = Temp[index2++];
		compareNum++;
		moveNum++;
	}
	while(index1 <= middle)
	{
		Array[j++] = Temp[index1++];
		compareNum++;
		moveNum++;
	}
	while(index2 <= right)
	{
		Array[j++] = Temp[index2++];
		compareNum++;
		moveNum++;
	}
}*/
template<class Elem>
void MergeSort<Elem>::print_m(Elem Array[] , int n)
{
	cout<<"        归并排序法         "<<endl;
	cout<<"+++++++++++++++++++++++++++"<<endl;
	cout<<"比较次数："<<compareNum<<endl;
	cout<<"移动次数："<<moveNum<<endl;
	//print(Array , n);
}
#endif