2waym.c

实训报告编码译码

/*              两路归并算法					*/
/*		作者：	毛剑辉		学号：200428014825038	*/
/*		日期：2004年10月3日				*/


#include <stdlib.h>
int mergesort(int p[], int n); 
extern int insertsort(int p[], int n);
static int merge(int work[], int swap[], int m, int n, int flag);
int mergeSort(int p[], int n);
static int merge_sort(int p[], int swap[], int n, int flag);




#define IN	1 
#define OUT	0
#define M	8 				/* 启始路段长度 */

int mergesort(int p[], int n)
{
	int op=0;
	int * work=p;
	int * swap;
	int i,j,m;
	int flag=OUT; 				/* 对换标志 */

	if (n<=16)
		return insertsort(work,n);
	swap=(int*)calloc(n,sizeof(int));
	if (swap==NULL) 
		return 0; 

	/* i 是经过插入排序的元素个数和未排序元素的开始位置 */
	for(i=0;i+M<=n;i+=M)	
		op+=insertsort(work+i,M);
	if (i<n)
		op+=insertsort(work+i,n-i);
	for(i=M; i<n; i<<=1,flag^=1) 		/* i 为路段长度 */
	{					 
		m=i<<1; 			/* m 为路段长度乘以归并的路数 */
		/* j 是已经归并路段的元素个数和未归并路段元素的开始位置 */
		for(j=0;j+m<=n;j+=m) 
			op+=merge(work+j,swap+j,i,m,flag); 
		if (j+i<n)
			op+=merge(work+j,swap+j,i,n-j,flag);
		else if (j<n)
			op+=merge(work+j,swap+j,n-j,n-j,flag);

	}
	if (flag==IN)
		op+=merge(work,swap,n,n,flag);

	free(swap);
	return op;
}

/*
 * 两路归并过程。
 */
static int merge(int work[],			/* 工作空间，就是要归并的列表 */
        	 int swap[],			/* 交换空间，不小于工作空间 */
                 int m,				/* 前半部分列表长度和后半部分列表的开始位置 */
                 int n, 			/* 列表总长度 */
                 int flag) 			/* 换入换出标志 */
{
	int *src, *dest;
	int i=0, j=m, t=0;

	if (flag==OUT) 
	{
		src=work;
		dest=swap;
	} 
	else 
	{ 
		src=swap;
		dest=work;
	} 

	while (i<m  && j<n) 
	{
		if (src[i] <= src[j]) 
			dest[t++] = src[i++];
		else
			dest[t++] = src[j++];

	}
	while (i<m) 
	{
		dest[t++] = src[i++];

	}
	while (j<n) 
	{
		dest[t++] = src[j++];

	}
	
	return n;
}

/**************************************/
/*   下面是递归原型实现		      */ 
/**************************************/
int mergeSort(int p[], int n)
{
	int op;
	int * temp;

	temp=(int*)calloc(n,sizeof(int));
	if (temp==NULL) 
		return 0;
	op=merge_sort(p,temp,n,IN);
	free(temp);
	return op;
}

static int merge_sort(int work[], int swap[], int n, int flag)
{
	int op=0; 

	if (n>1) {
		int m=n/2;
		op+=merge_sort(work,swap,m,flag^1);
		op+=merge_sort(work+m,swap+m,n-m,flag^1);
		op+=merge(work,swap,m,n,flag);
	}
	else if (flag == OUT) /* n==1 */
		swap[0]=work[0];
	

	return op;
}