mergesort.h

本文档讲解了几种排序方式的优缺点。包含直接插入、希尔、直接选择、冒泡、快速、堆、二路归并等排序方式。

/*----------------归并排序--------------------*/
void Merge(rectype *R,rectype *R1,long  low,long mid,long high)/*合并R的两个子表,结果有R1中*/
{
	long i,j,k;
	i=low;j=mid+1;k=low;
	while(i<=mid && j<=high)
		if(R[i].key<=R[j].key)   /*取小者复制*/
			R1[k++]=R[i++];
		else
			R1[k++]=R[j++];
	while(i<=mid) R1[k++]=R[i++];   /*复制左子表的剩余记录*/
	while(j<=high) R1[k++]=R[j++];  /*复制右子表的剩余记录*/
}

void MergePass(rectype *R,rectype *R1,long n,long len)/*对R做一趟归并,结果在R1中*/
{
	long i,j;
	i=1;                /*i指向第一对子表的起始点*/
	while(i+2*len-1<=n) /*归并长度为len的两个子表*/
	{
		Merge(R,R1,i,i+len-1,i+2*len-1);
		i=i+2*len;    /*i指向下一对子表起始点*/
	}
	if(i+len-1<n)    /*剩下两个子表,其中一个长度小于len*/
		Merge(R,R1,i,i+len-1,n);
	else
		for(j=i;j<=n;j++)
			R1[j]=R[j];
}  

void MergeSort(rectype *R,rectype *R1,long n)
{
	int len;
	len=1;
	while(len<n)
	{
		MergePass(R,R1,n,len);len=len*2;
		MergePass(R1,R,n,len);len=len*2;
	}
}