好库网 好库网首页 | 我的好库
VC开发指南

C语言实现归并排序

发布者:vchelp
发布日期:2013/5/12 16:48:59   更新日期:2013/5/12 16:48:59
阅读次数:2887
评分:4.80
介绍:归并排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
正文:

 

归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

归并排序中最常用的方法是:二路归并排序。二路归并的含义是把两个有序的序列合并成为一个有序的序列,基本思路是:将有N个记录的原始序列看作N个有序的子序列,每个子序列的长度为1,然后从第一个子序列开始,把相邻的子序列两两合并,得到[N/2]个长度为2或1的子序列(当子序列个数为奇数时,最后一组合并得到的序列长度为1),把这一过程称为一次归并排序。对第一次归并排序后的[N/2]个子序列采用上述方法继续顺序成对归并,如此重复,当最后得到长度为N的一个子序列时,该子序列便是原始序列归并排序后的有序序列。

 

源代码如下:

 

#include <stdio.h>

void Mpass(int x[],int y[],int k,int n);	/*声明其为函数*/
void Msort(int x[],int y[],int n);			/*声明其为函数*/

int main(void)
{
	/*要排序整型数据序列*/
	int a[] = {26,5,37,1,61,11,59,15,48,19};
	int y[10];				/*用于暂时存储数据*/
	int i;
	printf("源数据为:	   ");	/*将源数据打印出来*/
	for(i = 0;i<10;i++)
	printf("[%2d]",a[i]);
	Msort(a,y,10);		/*对源数据进行合并排序*/
	printf("\n排序后的数据为:  ");
	for(i = 0;i<10;i++)			/*将排序结果打印出来*/
	printf("%4d",a[i]);
	printf("\n");
	return 0;
}

void Mpass(x,y,k,n)
int x[];					/*要排序的数组*/
int y[];					/*用于存储临时数据的数组*/
int k;				/*表示当前序列中有若干长度为k的相邻有序子序*/
int n;				/*要排序序列的长度为n*/
	
{
	int i,j;
	int	strat1,end1;	/*对应第一个有序子序列L1起始和终止位置号*/
	int	strat2,end2;	/*对应第二个有序子序列L2起始和终止位置号*/
	int	m;				/*表示输入y中当前记录应放置的位置号*/
	strat1 = 0;
	m = 0;
	while(strat1+k<=n-1)		/*当第一个子序列没有占据整个x数组*/
	{
		strat2 = strat1+k;		/*为两个有序子序列起始终止位置号赋值*/
		end1 = strat2-1;
		/*如果第二的子序列长度不够k,则其终止位置号为n-1*/
		end2 = (strat2+k-1<=n-1)?strat2+k-1:n-1;
		for(i = strat1,j = strat2;i<=end1&&j<=end2;m++)
		{
			if(x[i]<=x[j])
			{
				y[m] = x[i];
				i++;
			}
			else
			{
				y[m] = x[j];
				j++;
			}
		}
		while(i<= end1)
		{
			y[m] = x[i];
			m++;
			i++;
		}
		while(j<= end2)
		{
			y[m] = x[j];
			m++;
			j++;
		}
		strat1 = end2+1;
	}
	/*将另一个序列中剩余的所有记录依次放到数组y中*/
	for(i=strat1;i<n;i++,m++)		
		y[m] = x[i];
}

void Msort(x,y,n)
int x[];			/*要排序的数组*/
int y[];			/*用于存储临时数据的数组*/
int n;				/*数组长度*/
{
	int i,k,count;
	k = 1;
	count = 1;
	while(k<n)				/*当子序列比整个序列小时*/
	{
		Mpass(x,y,k,n);		/*归并两有序子序列*/	
		for(i= 0;i<n;i++)
			x[i] = y[i];	/*返回数据*/
		printf("\n第%2d步后的结果==>  ",count++);
			for(i = 1;i<n+1;i++)
		{
			if((i ==n)&&((i%(2*k)!=0)))
				printf("%4d]",x[i-1]);
			else
			{
				if((i%(2*k)==1))
					printf("[%2d",x[i-1]);
				else if((i%(2*k))==0)
					printf("%4d]",x[i-1]);
				else
					printf("%4d",x[i-1]);
			}
		}
		k = 2*k;		/*一次归并后新的有序子序列的长度*/
	}
}

 

 

 


评论 [发表评论]
账号 密码 还没帐号呢,现在注册一个?

免责声明:好库网所展示的信息由买卖双方自行提供,其真实性、准确性和合法性由信息发布人负责。好库网不提供任何保证,并不承担任何法律责任。