Merge Sorted Array 合并两个有序数组

1.原题目

Given two sorted integer arrays A and B, merge B into A as one sorted array.

Note:

You may assume that A has enough space to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.

比如

int a[11] = {1,2,3,4,5};

int b[6] = {3,4,5,6,7,8};

要得到a[11] = {1,2,3,3,4,4,5,5,6,7,8}

2.归并排序的其中一步

第一感觉这个题目比较简单，就是归并排序中的其中一步：

需要一个tmp数组，初始化两个int 作为指示器，分别指向a数组的第一个元素和b数组的第一个元素。

然后比较a数组和b数组的当前元素，谁比较小谁就放入tmp数组。完了后移向下一个元素。这样操作直到a指示器大于a数组长度或者b指示器大于b数组长度。

然后看a数组和b数组，谁还剩下元素就把谁全部复制到tmp数组中。

tmp数组就是最终的有序数组。

void merge(int A[], int m, int B[], int n) {

	int aIndex, bIndex,tmpIndex;
	aIndex = bIndex = tmpIndex = 0;
	int* tmp = new int[m + n];

	while(aIndex < m && bIndex < n){
	if(A[aIndex] <= B[bIndex]){
	tmp[tmpIndex++] = A[aIndex++];
	}else{
	tmp[tmpIndex++] = B[bIndex++];
	}
	}
        //如果a数组还有剩下，就复制a的到tmp
	while(aIndex < m){
	tmp[tmpIndex++] = A[aIndex++];
	}
        //如果b数组还有剩下，就复制b的到tmp
	while(bIndex < n){
	tmp[tmpIndex++] = B[bIndex++];
	}
        //最后再把tmp复制到a数组
         for(int i = 0; i < m + n; ++i){
	A[i] = tmp[i];
	}
	delete tmp;
}

3.为什么需要一个额外的tmp数组？

脑子被归并排序给先入为主弄傻了。因为归并排序是对一个数组进行操作，往往需要一个额外的数组来存储。这道题目中，a数组空间比较大，可以直接用a

换个思路，

初始化两个int 作为指示器，分别指向a数组的最后一个元素和b数组的最后一个元素。

然后比较大小，较大的放入a数组的末端。这样不断往前走。直到a数组用完或者b数组用完。

如果a数组先用完，那么就把b数组剩下的所有元素复制到a的前半部分，如果b数组先用完，那么a数组已经是一个有序的数组。

void merge(int A[], int m, int B[], int n) {

	int larstAIndex = m - 1;
	int larstBIndex = n - 1;
	int currentIndex = m + n - 1;

	while(larstAIndex >= 0 && larstBIndex >= 0){
		if(A[larstAIndex] >= B[larstBIndex]){
			A[currentIndex--] = A[larstAIndex--];
		}else{
			A[currentIndex--] = B[larstBIndex--];
		}
	}
	while(larstBIndex >= 0){
		A[currentIndex--] = B[larstBIndex--];
	}

}

http://www.waitingfy.com/archives/1012

数据结构 & 算法 | RSS 2.0 |