题目
原文：
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.
译文：
A和B是两个有序数组(假设为递增序列)，而且A的长度足以放下A和B中所有的元素， 写一个函数将数组B融入数组A，并使其有序。
解答
最简单的方法是开一个大小可以容纳A和B的数组C，然后像归并排序中合并两个数组一样， 按照大小顺序把数组A和数组B的元素一一地放入数组C，然后再将数组C拷贝给A。 这种方法额外地使用了O(n)的空间，显然这是没有必要的开销。由于A的大小已经足够用了， 所以直接在A上直接操作即可。
可是如果我们思维定势地对比数组A和数组B，每次取小的元素放入数组A， 这样就会发现，要放入的位置上正放着有用的元素。处理起来就麻烦了。
相反，如果我们从A和B的尾部元素开始对比，每次取大的元素放在数组A的尾部， 这样一来，要放入的位置就不会出现上面的冲突问题。当对比结束时， 即可得到一个排好序的数组A。代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
using namespace std;
void merge(int a[], int b[], int n, int m){
int k = n + m - 1;
int i = n - 1, j = m - 1;
while(i>=0 && j>=0){
if(a[i] > b[j]) a[k--] = a[i--];
else a[k--] = b[j--];
}
while(j>=0) a[k--] = b[j--];
}
int main(){
int a[15] = {
1, 3, 7, 8, 9
};
int b[] = {
2, 4, 5, 6, 10
};
int n = 5, m = 5;
merge(a, b, 5, 5);
for(int i=0; i<m+n; ++i)
cout<<a[i]<<" ";
return 0;
}
对比结束后，要检查数组B中是否还有元素，有的话要将它们拷贝到数组A。 我们并不需要检查数组A，因为如果数组A还有元素，说明while循环是因为数组B 中没有元素了才退出的。而A中的元素本来就是有序且就位于数组A中，所以不需要再管它。 如果A和B中的元素个数为n和m，则该算法的时间复杂度为O(n+m)。
让我们再加点限制条件，如果两个有序的序列并且没有额外的空间，那要怎么排序。 比如对于数组A，它的前半段和后半段分别有序，不使用额外的空间怎么使A整体有序。
首先，不可避免的我们还是要将两个有序部分中的元素拿出来对比。 我们先拿出前半段的第一个元素和后半段的第一个元素进行对比， 如果后半段的第一个元素要小，就将它们交换。由于这两个元素是各自序列的最小值， 这一对比就将整个数组A的最小值取出放在了正确的位置上。然后呢？ 交换到后半段的那个值怎么办？不理它，不太合适吧。我们可以通过两两对比， 把它移动到后半段的某个位置，使后半段保持有序。接下来呢？ 我们取出前半段的第2个元素(第1个元素已经放在它正确的位置上，不用理它了)， 还是和后半段的第1个元素对比，这一对比中较小的就会是整个数组中第2小的元素， 如果是后半段那个元素较小，则交换它们，然后仍然移动后半段使其保持有序。 这样不断进行下去，当把前半段的元素都遍历操作一遍，就会将小的元素都移动到前半段， 并且是有序的。而大的元素都在后半段且也是有序的。排序结束。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
using namespace std;
void swap(int &a, int &b){
a = a^b;
b = a^b;
a = a^b;
}
void merge(int a[], int begin, int mid , int end){
for(int i=begin; i<=mid; ++i){
if(a[i]>a[mid+1]){
swap(a[i], a[mid+1]);
for(int j=mid+1; j<end; ++j){
if(a[j]<=a[j+1]) break;
swap(a[j], a[j+1]);
}
}
}
}
int main(){
int a[10] = {
8, 9, 11, 15, 17, 1, 3, 5, 12, 18
};
int b[10] = {
1, 2, 3, 4, 5, 6, 7, 8, 9, 10
};
merge(a, 0, 4, 9);
for(int i=0; i<10; ++i)
cout<<a[i]<<" ";
return 0;
}
全书题解目录：
Cracking the coding interview–问题与解答
全书的C++代码托管在Github上：
https://github.com/Hawstein/cracking-the-coding-interview
声明：自由转载-非商用-非衍生-保持署名 | 创意共享3.0许可证，转载请注明作者及出处
出处：http://hawstein.com/2013/01/16/9.1/
