ソートされた 2 つの配列 A と B があり、A の末尾に B を格納するのに十分なスペースがある場合、B を A にマージしてソートするメソッドを作成します。
この質問を受け取った後の最も直接的なアイデアは、A と B の要素を比較し、A と B のすべての要素が走査されるまでそれらを順番に配列に挿入することです。ただし、これには欠点があります。要素の挿入位置が配列 A の前にある場合、元の配列を後方に移動する必要があります。これによりオーバーヘッドが追加されます。ただし、別の方法を使用して配列 A の末尾に要素を挿入することもできます。こうすることで要素は移動しなくなります。コードは次のとおりです。
次のようにコード code をコピーします: /*
* lastA: a の実際の要素数 lastB: b の実際の要素数 mergeIndex は新しい配列の実際の空間サイズ
*/
public static void mergeOrder(int[] a, int[] b, int lastA, int lastB) {
int インデックス A = lastA - 1;
int インデックス B = lastB - 1;
int mergeIndex = lastA + lastB - 1;
while (インデックス A >= 0 && インデックス B >= 0) {
if (a[インデックスA] > b[インデックスB]) {
a[マージインデックス] = a[インデックスA];
マージインデックス --;
インデックスA --;
} それ以外 {
a[マージインデックス] = b[インデックスB];
マージインデックス --;
インデックスB --;
}
}
while (インデックス B >= 0) {
a[マージインデックス] = b[インデックスB];
マージインデックス --;
インデックスB --;
}
}