improvedtwowaymergesorter.h

实现各种排序算法

//优化的两路归并排序类

#include "ImprovedInsertSorter.h"
#define THRESHOLD 16

template <class Record,class Compare>
class ImprovedTwoWayMergeSorter:public Sorter<Record,Compare>
{
private:
	Record * TempArray;
	void Merge(Record Array[],int left,int right,int middle);	//归并过程
public:
	ImprovedTwoWayMergeSorter();
	~ImprovedTwoWayMergeSorter();
	void Sort(Record Array[],int left, int right);
};

template <class Record,class Compare>
ImprovedTwoWayMergeSorter<Record,Compare>::ImprovedTwoWayMergeSorter()
{
	TempArray = new Record[1000000];
}

template <class Record,class Compare>
ImprovedTwoWayMergeSorter<Record,Compare>::~ImprovedTwoWayMergeSorter()
{
	delete[] TempArray;
}

//优化的两路归并排序，Array[]为待排序数组，left，right分别为数组两端
template <class Record,class Compare>
void ImprovedTwoWayMergeSorter<Record,Compare>::Sort(Record Array[], int left, int right) 
{ 
	if (right <= left)					// 如果只含有一个元素，直接返回
		return;    
	if (right-left+1 <= THRESHOLD)
	{
		ImprovedInsertSorter<Record,Compare> insert_sorter;
		insert_sorter.Sort(&Array[left],right-left+1);
	}
	else
	{
		int middle=(left+right)/2;		//从中间划分为两个子序列
		Sort(Array,left,middle);		//对左边一半进行递归
		Sort(Array,middle+1,right);		//对右边一半进行递归
		Merge(Array,left,right,middle);	// 进行归并
	}

}

//归并过程
template <class Record,class Compare>
void ImprovedTwoWayMergeSorter<Record,Compare>::Merge(Record Array[],int left,int right,int middle)
{
	int index1,index2;				//两个子序列的起始位置
	int i,j,k ;
	for (i=left; i<=middle; i++)	//复制左边的子序列
		TempArray[i] = Array[i];
	for (j=1; j<=right-middle; j++)	//复制右边的子序列，但顺序颠倒过来
		TempArray[right-j+1] = Array[j+middle];
	// 开始归并
	for (index1=left,index2=right,k=left; k<=right; k++)
		if (Compare::lt(TempArray[index1], TempArray[index2]))
			Array[k] = TempArray[index1++];
		else Array[k] = TempArray[index2--];
}