mgsort.c

从各种VC源码中精选出来

//归并排序算法设计。

#define MAX 16   	//元素个数的最大值

int R[MAX]={9,2,13,5,10,16,17,11,4,6,8,1,7} ; //用数组来储存元素
int R1[MAX]; 		//辅助数组

//归并两个有序文件段 ： 
MERGE ( int P[ ],int Q[ ],int low,int mid,int high )
{	int	i,j,k;
	i=low;j=mid;k=low;
	while ( i<mid && j<high )		//取小者复制
		if ( P[i] <= P[j] ) Q[k++] = P[i++];
		else Q[k++] = P[j++];
	while ( i<mid )  Q[k++] = P[i++];//复制第一个文件的剩余元素
	while ( j<high )  Q[k++] = P[j++];//复制第二个文件的剩余元素
}

//对文件进行一遍归并操作 ： 
MERGEPASS ( int M[ ], int N[ ],int length,int n)
{	int	i,j;
	i = 0;	//指向第一对子文件的起始端
	while ( i + 2*length - 1 < n ) {//归并两个长度为length的子文件
		MERGE ( M,N,i,i+length,i+2*length ) ;
		i+=2*length;		//指向下一对子文件的起始端
		}
	if  ( i + length < n )
		MERGE ( M,N,i,i+length,n ) ; //第二个子文件长度小于length
	else for ( j=i;j<n;j++ ) N[j] = M[j] ;//将最后一个子文件复制到N中
}

//对整个文件进行二路归并排序 ： 
MERGESORT (int S[ ], int D[ ],int n) //排序结果仍然在S[ ]中
{
	int length = 1;	//从单个元素开始进行归并
	while ( length < n ) {	//只要整个文件还可以分成两个以上子文件
		MERGEPASS ( S,D,length,n); //进行一遍归并：S[n] ---> D[n]
		length *= 2; //加大子文件的长度
		MERGEPASS ( D,S,length,n); //再进行一遍归并，结果返回到S[ ]中
		length *= 2; //加大子文件的长度
		}
}

main ( )
{   
	int n=13;		//实际元素个数
	MERGESORT (R,R1,n); //调用归并排序算法
	while (1) ; //在这一行设置断点,中止程序运行,以便观察程序运行的结果 
}