ここでは、O(n) 時間以内に完了できる効率的なアルゴリズムを紹介します。
中心となるアイデアは、2 つのポインターを定義し、1 つのポインター A が前から後ろにスキャンし、1 つのポインター B が後ろから前にスキャンするというものです。ポインタ A は偶数にスキャンして一時停止し、ポインタ B は奇数にスキャンして一時停止し、交換後、ポインタ A とポインタ B が一致して停止するまで、上記と同様にスキャンと交換を続けます。
このアルゴリズムの Java コードは次のとおりです。
次のようにコードをコピーします。
パッケージの再注文;
パブリック クラス 並べ替え {
public static void main(String[] args) {
int[] リスト = { 1, 2, 3, 4, 5, 7, 9, 11 };
reorderOddEven(リスト);
}
public static void reorderOddEven(int[] list) {
int 長さ = list.length;
for (int i = 0; i < length; i++) {
System.out.print(list[i] + " ");
}
System.out.print("/n");
int 開始 = 0;
int 終了 = 長さ - 1;
while (開始 < 終了) {
while (begin < end && (list[begin] & 0x1) != 0)
開始++;
while (開始 < 終了 && (リスト[終了] & 0x1) == 0)
終わり - ;
if (開始 < 終了) {
int temp = リスト[開始];
リスト[開始] = リスト[終了];
リスト[終了] = 一時;
}
}
for (int i = 0; i < length; i++) {
System.out.print(list[i] + " ");
}
}
}