mergesort2.h

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

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

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

void MergeSort2(rectype *R,rectype *R1,long n,long low,long high)
{
	long mid;
	if(low>=high) return;
	mid=(low+high)/2;
    MergeSort2(R,R1,n,low,mid);
	MergeSort2(R,R1,n,mid+1,high);
	Merge2(R,R1,low,mid,high);
}