首页 > 代码库 > 二路归并排序(也叫合并排序)

二路归并排序(也叫合并排序)

下面这图展示了二路归并的过程


二路归并的核心代码是merge()函数

它将2个分割的数组有序的合并在一起

如图:

在数组A中,

从p到q是一个数组,从q到r是另外一个数组

那么如何将这2个数组有序的合并在一起,组个新的数组A呢?

步骤:

第一步:开辟一个数组L,存放p到q之间(也就是需要归并的左边数组)的元素

第二部:开辟一个数组R,存放q到r之间(也就是需要归并的右边数组)的元素

第三步:2个数组的最后还要加一个无穷大的数(可以用0x7FFF表示),因此开辟的数组空间要多1字符个空间

第四步:L与R中的数字逐个比较,把较小的先放在数组A中(从数组A【0】开始存放,依次往后覆盖原来的数),然后较小的数组指针往后移动,指向下一位再和另外一个数组比较



//第一个参数为需要排序的数组,第2个参数为分割的第一个数组开始元素的下标
//第3个参数为分割的第一个数组的最后1个元素的下标
//第4个参数为数组最后1个元素的下标
void Merge(int *A,int p,int q,int r)
{
	int n1,n2,i,j,k,g;
	n1=q-p+1;
	n2=r-q;
	int *L,*R;
	L=(int *)malloc(sizeof(int)*(n1+1)); 
	R=(int *)malloc(sizeof(int)*(n2+1));
	L[n1]=0x7fff; //开辟的左右2个数组最后1个数设置为最大值
	R[n2]=0x7fff;
	g=0;
	for(i=p;i<=q;i++)
	{
		L[g]=A[i];
		g++;
	}
	g=0;
	for(i=q+1;i<=r;i++)
	{
		R[g]=A[i];
		g++;
	}
	//逐个比较左右两组数组,把较小的值写入原来的数组
	j=k=0;
	for(i=p;i<=r;i++)
	{
		if(L[j]<R[k])
		{
			A[i]=L[j];
			j++;
		}
		else
		{
			A[i]=R[k];
			k++;
		}
	}
}

完整代码:

#include<iostream>
using namespace std;

//第一个参数为需要排序的数组,第2个参数为分割的第一个数组开始元素的下标
//第3个参数为分割的第一个数组的最后1个元素的下标
//第4个参数为数组最后1个元素的下标
void Merge(int *A,int p,int q,int r)
{
	int n1,n2,i,j,k,g;
	n1=q-p+1;
	n2=r-q;
	int *L,*R;
	L=(int *)malloc(sizeof(int)*(n1+1)); 
	R=(int *)malloc(sizeof(int)*(n2+1));
	L[n1]=0x7fff; //开辟的左右2个数组最后1个数设置为最大值
	R[n2]=0x7fff;
	g=0;
	for(i=p;i<=q;i++)
	{
		L[g]=A[i];
		g++;
	}
	g=0;
	for(i=q+1;i<=r;i++)
	{
		R[g]=A[i];
		g++;
	}
	//逐个比较左右两组数组,把较小的值写入原来的数组
	j=k=0;
	for(i=p;i<=r;i++)
	{
		if(L[j]<R[k])
		{
			A[i]=L[j];
			j++;
		}
		else
		{
			A[i]=R[k];
			k++;
		}
	}
}

void MergeSort(int *A,int p,int r)
{
	int q;
	if(p<r) //当第一个元素比最后1个元素还小时,继续执行递归,直到只剩下一个元素(形参p=r)
	{
	q=(p+r)/2;
	MergeSort(A,p,q);
	MergeSort(A,q+1,r);
	Merge(A,p,q,r);
	}
}

void main()
{
	int A[5]={5,3,4,23,11};
	MergeSort(A,0,4);
	for(int i=0;i<5;i++)
		cout<<A[i]<<endl;
	system("pause");
}




二路归并排序(也叫合并排序)