- 思路
當一個數組的空間足夠大時可以將兩個有序數組從后向前排序以提升效率。
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;
}
