mergesort.h

采用随机数来生成要排序的内容

#ifndef MERGESORT_H_
#define MERGESORT_H_
#include "List.h"
#include<time.h>
#include<stdlib.h>
template<class Record>
class Mergesort:public List<Record>
{
   public: 
	   Mergesort();   
	   void rand_seed();
	   Record rand_record(Record a,Record b);
	   void print(List<Record>list);
	   void Merge(List<Record>&source,List<Record>&dest,int low ,int mid,int high);
	   void MergePass(List<Record>&source,List<Record>&dest,int n,int len);
	   void StartSort(List<Record>&source,List<Record>&dest,int n);
   private:
	   int count;
};
template<class Record>
Mergesort<Record>::Mergesort()
{
	count=0;
}
template<class Record>
void Mergesort<Record>::rand_seed()
{
    int seed=static_cast<int>(time(0));
	srand(seed);
}
template<class Record>
Record Mergesort<Record>::rand_record(Record a,Record b)
{
    return a+rand()%(b-a+1);
}
template<class Record>
void Mergesort<Record>::print(List<Record>list)
{
	Record data;
	cout<<"第"<<(count++)<<"次归并:";
	for(int i=1;i<list.size();i++)
	{
		list.retrieve(i,data);
		cout<<data<<" ";
	}		
		cout<<endl;	
}
template<class Record>
void Mergesort<Record>::Merge(List<Record>&source,List<Record>&dest,int low ,int mid,int high)
{
	int i,j,k;
	Record data1,data2;
	i=low;j=mid+1;k=low;
	while(i<=mid&&j<=high)
	{
		source.retrieve(i,data1);
		source.retrieve(j,data2);
		if(data1<=data2) 
		{
			dest.replace(k++,data1);
			i++;
		}
		else 
		{
			dest.replace(k++,data2);
			j++;
		}			
	}	
	while (i<=mid) 
	{
		source.retrieve(i++,data1);
		dest.replace(k++,data1);
	}
	while (j<=high) 
	{
		source.retrieve(j++,data2);
		dest.replace(k++,data2);
	}			
}
template<class Record>
void Mergesort<Record>::MergePass(List<Record>&source,List<Record>&dest,int n,int len)
{
	int i=1,j;
	Record data;	
	while(i+2*len-1<=n){
		Merge(source,dest,i,i+len-1,i+2*len-1);
		i=i+2*len;
	}
	if(i+len-1<n)
		Merge(source,dest,i,i+len-1,n);
	else 
		for(j=i;j<=n;j++){
			source.retrieve(j,data);		
			dest.replace(j,data);
		}
	print(dest);
}
template<class Record>
void Mergesort<Record>::StartSort(List<Record>&source,List<Record>&dest,int n)
{
	int len=1;	
	while(len<n){	
		MergePass(source,dest,n,len);len*=2;			
		MergePass(dest,source,n,len);len*=2;
	}	
}
#endif