- 思路
当一个数组的空间足够大时可以将两个有序数组从后向前排序以提升效率。
2.代码
#include <iostream>
#define N 100 //数组的最大长度
using namespace std;
int main(int argc, const char * argv[]) {
//假设两个数组中有一个数组的空间足够大到容纳两个数组，因此可以将两个数组合并到这个空间足够大的数组中，这里选择a1
int a1[N] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
int a2[N] = {2, 4, 6, 8, 10, 12, 14, 16, 18};
int len1 = 10;
int len2 = 9;
//从后向前比较，初始化两个数组当前比较位置的下表和当前插入位置的下标
int cur1 = len1 - 1;
int cur2 = len2 - 1;
int cur3 = len1 + len2 - 1;
//当两个数组都同时还有元素未必较完时
while(cur1 >= 0 && cur2 >= 0) {
if(a1[cur1] > a2[cur2]) {
a1[cur3] = a1[cur1];
cur1--;
}
else {
a1[cur3] = a2[cur2];
cur2--;
}
cur3--;
}
//当a1数组有剩余元素没比较时无需移动，因为已到它的最终位置
//当a2数组有剩余元素没比较时直接将剩下的元素拷贝到a1数组的前端
if(cur2 >= 0) {
while( cur2 >= 0 ) {
a1[cur2] = a2[cur2];
cur2--;
}
}
for(int i = 0;i < len1 + len2;i++)
cout<<a1[i]<<" ";
return 0;
}
