給定兩個排序後的數組A和B,其中A的末端有足夠的空間容納B,編寫一個方法將B合併到A併排序。
拿到這個題後，最直接的想法就是比較A和B中的元素，並依序插入數組，直到遍歷完A和B中的所有元素。但這樣做會有一個不好的地方：如果元素的插入位置在陣列A的前端，那就必須將原來的陣列往後移動。這會增加開銷。但是我們可以用另外的一種辦法將元素插入陣列A的末端。這樣我們不會出現元素移動的狀況！代碼如下:
複製代碼代碼如下: /*
* lastA:a中的實際元素數lastB:b中的實際元素數mergeIndex是新陣列的實際空間大小
*/
public static void mergeOrder(int[] a, int[] b, int lastA, int lastB) {
int indexA = lastA - 1;
int indexB = lastB - 1;
int mergeIndex = lastA + lastB - 1;
while (indexA >= 0 && indexB >= 0) {
if (a[indexA] > b[indexB]) {
a[mergeIndex] = a[indexA];
mergeIndex --;
indexA --;
} else {
a[mergeIndex] = b[indexB];
mergeIndex --;
indexB --;
}
}
while (indexB >= 0) {
a[mergeIndex] = b[indexB];
mergeIndex --;
indexB --;
}
}