mergesort.cpp

归并排序算法实现

/*归并排序的C++语言描述*/
#include<iostream.h>
#include<stdlib.h>
#include<windows.h>

#define N 2000

template<class T>void MergeSortL(T A[],T Link[],int low,int high,int &p);
template<class T>void MergeL(int q,int r,int &p);
template<class T>void InsertSort(T A[],T Link[],int low,int high,int &p);

void main()
{
	int const ARRAYLG(1000);//数组长度
	int a[ARRAYLG+1];
	int link[ARRAYLG+1];
	int begin=0;
	a[0]=-1;
	link[0]=0;
	for(int i=1;i<=ARRAYLG;i++)//给数组赋值
	{
		a[i]=rand()%N;
		link[i]=0;
	}
	LARGE_INTEGER litmp;
	LONGLONG QPart1,QPart2;
	double dfMinus,dfFreq,dfTim;
	QueryPerformanceFrequency(&litmp);
	dfFreq=(double)litmp.QuadPart;//获得计数器的时钟频率
	QueryPerformanceCounter(&litmp);
	QPart1=litmp.QuadPart;//获得初始值

	MergeSortL(a,link,1,ARRAYLG,begin);//排序

	QueryPerformanceCounter(&litmp);
	QPart2=litmp.QuadPart;//获得中止值
	dfMinus=(double)(QPart2-QPart1);
	dfTim=dfMinus/dfFreq;//获得对应的时间值，单位为秒
	cout<<"The total time is:"<<dfTim<<" seconds."<<endl;
	/*for(i=0;i<=ARRAYLG;i++)
	{
		cout<<a[i]<<" ";
	}
	cout<<endl;
	for(i=0;i<=ARRAYLG;i++)
	{
		cout<<link[i]<<" ";
	}
	cout<<endl;
	*/
}

template<class T>
void MergeSortL(T A[],T Link[],int low,int high,int &p)
/*Link是数组A[low:high]的下标表,p指示这个表的开始处。利用Link将A按非降顺序排列*/
{
	if(high-low+1<4)//设定子问题的最小规模
		InsertSort(A,Link,low,high,p);
	else
	{
		int mid=(low+high)/2;
		int q=0;
		MergeSortL(A,Link,low,mid,q);//返回q表
		int r=0;
		MergeSortL(A,Link,mid+1,high,r);//返回r表
		MergeL(A,Link,q,r,p);//将表q和r合并成表p
	}
}

template<class T>
void MergeL(T A[],T Link[],int q,int r,int &p)
/*由链接表q和r构造新的连接表p。q,r是数组Link[1:n]中两个表指针，这两个链表指出被划分的两个子组的
地址排序，而p指针指出两组归并后的地址排序。实际上都是表的相互顺序在变*/
{
	int i=q,j=r,k=0;//定义及初始化，新表在Link[0]处开始
	while(i!=0&&j!=0)//当两个表皆非空时
	{
		if(A[i]<=A[j])
		{
			Link[k]=i;
			k=i;
			i=Link[i];//加一个新元素到此表
		}
		else
		{
			Link[k]=j;
			k=j;
			j=Link[j];
		}
	}
	if(i==0)
		Link[k]=j;
	else
		Link[k]=i;
	p=Link[0];
}

template<class T>
void InsertSort(T A[],T Link[],int low,int high,int &p)//插入排序算法
{	
	Link[0]=low;
	for(int i=low+1;i<=high;i++)
	{
		T t=A[i];
		int j=0,temp=0;
		for(j=Link[0];j!=0&&t>=A[j];temp=j,j=Link[j])
			;
		if(j!=0)
		{
			Link[i]=j;
			Link[temp]=i;
		}
		else
		{
			Link[temp]=i;
		}
	}
	p=Link[0];
}