mergingsort.cpp

各种内部排序算法的实现和比较

#include "base.h"

void Merge(RedType SR[],RedType TR[],int i,int m,int n)
{//将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n]
	int j,k;
	int a,b;
	
	for(j=m+1,k=i;i<=m&&j<=n;k++)			//将SR中记录由小到大地并入TR
	{
		if(LT(SR[i].key,SR[j].key))
		{
			TR[k]=SR[i];
			i++;
		}
		else
		{
			TR[k]=SR[j];
			j++;
		}
	}
	if(i<=m)								//将剩余的SR[i..m]复制到TR
	{
		for(a=k,b=i;a<=n&&b<=m;a++,b++)
			TR[a]=SR[b];
	}
	if(j<=n)								//将剩余的SR[j..n]复制到TR
	{
		for(a=k,b=j;a<=n&&b<=n;a++,b++)
			TR[a]=SR[b];
	}
}

void MSort(RedType SR[],RedType TR1[],int s,int t)
{//将SR[i..t]归并排序为TR1[s..t]
	int m;
	RedType *TR2;
	TR2=new RedType[MAXSIZE+1];

	if(s==t)
		TR1[s]=SR[s];
	else
	{
		m=(s+t)/2;						//将SR[s..t]平分为SR[s..m]和SR[m+1..t]
		MSort(SR,TR2,s,m);				//递归地将SR[s..m]归并为有序的TR2[s..m]
		MSort(SR,TR2,m+1,t);			//递归地将SR[m+1..t]归并为有序的TR2[m+1..t]
		Merge(TR2,TR1,s,m,t);			//将TR2[s..m]和TR2[m+1..t]归并到TR1[s..t]
	}
	delete []TR2;
}

void MergeSort(SqList &L)
{//归并排序
	MSort(L.r,L.r,1,L.length);
}