陣列原地重排序：O(n) 雙指針法將奇數前置偶數後置

問題描述

給定整數陣列，要求在 O(n) 時間、O(1) 空間 內完成重排，使所有奇數位於偶數之前。

核心算法：雙指針對撞交換

1. 左指針 begin 從頭向後掃描，遇到偶數停下
2. 右指針 end 從尾向前掃描，遇到奇數停下
3. 若 begin < end，交換兩元素，繼續掃描
4. 指針相遇即結束

Java 實現

public class ArrayReorder {
    public static void reorderOddEven(int[] arr) {
        int begin = 0, end = arr.length - 1;
        while (begin < end) {
            // 向右找偶數
            while (begin < end && (arr[begin] & 1) != 0) begin++;
            // 向左找奇數
            while (begin < end && (arr[end] & 1) == 0) end--;
            if (begin < end) {
                int tmp = arr[begin];
                arr[begin] = arr[end];
                arr[end] = tmp;
            }
        }
    }

    public static void main(String[] args) {
        int[] data = {1, 2, 3, 4, 5, 7, 9, 11};
        System.out.println("Before: " + Arrays.toString(data));
        reorderOddEven(data);
        System.out.println("After:  " + Arrays.toString(data));
    }
}

關鍵技術點解析

• (x & 1) != 0 位運算判斷奇數，比取模更高效
• 雙重 while 保證指針不越界且精準定位待交換元素
• 原地交換，空間複雜度 O(1)
• 單次遍歷，時間複雜度 O(n)

擴展應用

同樣模板可解決：

• 負數前置、正數後置
• 能被 3 整除的數前置
• 任意單一條件的二分區劃（Partition）問題

測試輸出示例

Before: [1, 2, 3, 4, 5, 7, 9, 11]
After:  [11, 9, 7, 5, 3, 1, 4, 2]  // 奇數全在前，偶數全在後，順序不保證