首页 > 代码库 > 分治——合并排序

分治——合并排序

2024-07-12 18:01:45   222人阅读

分治策略中有一个经典的算法就是合并排序，这个算法的精髓也是分治二字，分而治之。将一个大规模的问题分割成若干个同样的小问题，小问题的规模很小，很容易解决，解决了小的问题后再对这些小问题的结果进行合并得到大规模问题的解答。

合并排序便是分治策略中比较经典的算法，首先是合并，两个排列有序的数列经过合并后成为有序的数组：代码如下:

void _merge(int *A,int left,int middle,int right)
{
	int i=left,j=middle+1,k=0;
	int *C;
	C=new int[right-left+1];
	while(i<middle+1 && j<right+1)
	{
		if(A[i]<A[j])
		{
			C[k++]=A[i++];
		}
		else
		{
			C[k++]=A[j++];
		}
	}
	while(i<middle+1)
		C[k++]=A[i++];
	while(j<right+1)
		C[k++]=A[j++];
	for(int i=0;i<right-left+1;i++)
	{
		A[i+left]=C[i];
	}
	delete[] C;
}
上面的算法是将一个数组分成左右两个进行合并，如果这左右的两个数组都是排列有序的话，那么合成的新的数列也是有序的，下面的任务就是怎么将左右的两个数列排列成有序的，方法就是用递归思想，不断的递归，将数列不断的划分，划分成最小的单元，只有一个数的时候，那么再进行合并，合并成的数列便是有序数列了，代码如下：

void _merge_sort(int *A,int left,int right)
{
	
	if(left<right)
	{
		int middle=(left+right)/2;
		_merge_sort(A,left,middle);
		_merge_sort(A,middle+1,right);
		_merge(A,left,middle,right);
	}
}
最后进行测试：

void main()
{
	int ib[]={2,3,1,0,9,1,3,5};
	int length=sizeof(ib)/sizeof(int);
	_merge_sort(ib,0,length-1);
	for(int i=0;i<length;i++)
	{
		cout<<ib[i]<<' ';
	}
}
结果如下：


联系
我们