爱悠闲 > 两个已排序数组的归并

两个已排序数组的归并

分类: Cracking the coding interview  |  作者: kingbird_wang 相关  |  发布日期 : 2014-07-08  |  热度 : 513°

Cracking the coding interview 9.1

You are given two sorted arrays, A and B, and A has a large enough buffer at the end to hold B. Write a method to merge B into A in sorted order.

思路:从后向前归并。这里有个问题需要注意一下,两个数组的内存区域不能有重叠的部分,否则在归并的过程中会出错。所以在函数入口处做了这个检查。

void MergeArray(int *parrA, int nlengthA, int *parrB, int nlengthB)
{
	assert((parrB > parrA + nlengthA + nlengthB - 1) ||
		   (parrA > parrB + nlengthB - 1)); // make sure no overlap on ArrA and ArrB
	
	int *pA = parrA + nlengthA - 1;
	int *pB = parrB + nlengthB - 1;
	int *pOut = parrA + nlengthA + nlengthB - 1;
	while (pA >= parrA && pB >= parrB)
		{
		if(*pA > *pB)
			{
			*pOut = *pA;
			pA--;
			}
		else
			{
			*pOut = *pB;
			pB--;
			}
		pOut--;
		}
	while (pB >= parrB)
		{
		*pOut = *pB;
		pB--;
		pOut--;
		}
}