您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 程式設計入門

陣列重排序：雙指針 O(n) 將奇數移至偶數前端

編輯：Java 程式設計入門

給定整數陣列，原地重排使所有奇數位於偶數之前，要求 O(n) 時間、O(1) 空間。經典雙指針對撞演算法完美解決，本文從邏輯推導、程式碼實現、邊界測試、擴展應用四維度詳細解析。

核心邏輯：雙指針對撞

left 從左向右掃描，遇到偶數停下
right 從右向左掃描，遇到奇數停下
交換 a[left]、a[right]
繼續直到 left >= right

判斷奇偶：位運算 `(x & 1) != 0`

// 奇數：最低位為 1
(x & 1) == 1  // 或 != 0

// 偶數：最低位為 0
(x & 1) == 0

比 x % 2 更快，無負數餘數困擾。

Java 完整實現

public class ReorderOddEven {

    /** 原地重排：奇數前、偶數後 */
    public static void reorderOddEven(int[] arr) {
        if (arr == null || arr.length <= 1) return;

        int left = 0;
        int right = arr.length - 1;

        while (left < right) {
            // 左指針找偶數
            while (left < right && (arr[left] & 1) != 0) {
                left++;
            }
            // 右指針找奇數
            while (left < right && (arr[right] & 1) == 0) {
                right--;
            }
            // 交換
            if (left < right) {
                int tmp = arr[left];
                arr[left] = arr[right];
                arr[right] = tmp;
                left++;
                right--;
            }
        }
    }

    // 測試
    public static void main(String[] args) {
        int[] a = {1, 2, 3, 4, 5, 7, 9, 11};
        System.out.println("Before: " + Arrays.toString(a));
        reorderOddEven(a);
        System.out.println("After:  " + Arrays.toString(a));
        // 輸出: [11, 9, 7, 5, 3, 4, 2, 1] (奇數順序可能改變)
    }
}

關鍵細節

細節	處理方式
內層循環條件	`left < right` 必須放在最前，防止指針越界
交換後指針移動	`left++; right--;` 避免死循環
全奇/全偶陣列	外層 `while` 直接結束，零交換
負數處理	`& 1` 正確判斷負奇數 (如 -3 & 1 = 1)

穩定性說明

此演算法不穩定：相對順序會改變 (如範例中 1,3,5,7,9,11 變為 11,9,7,5,3,1)。若需穩定分區 (保持奇數間、偶數間相對順序)，需 O(n) 額外空間或 O(n log n) 時間 (歸併分區)。

擴展應用：泛化分區 (Partition)

/** 依 predicate 分區：true 在前，false 在後 */
public static <T> void partition(T[] arr, Predicate<T> pred) {
    int l = 0, r = arr.length - 1;
    while (l < r) {
        while (l < r && pred.test(arr[l])) l++;
        while (l < r && !pred.test(arr[r])) r--;
        if (l < r) {
            T tmp = arr[l];
            arr[l] = arr[r];
            arr[r] = tmp;
            l++; r--;
        }
    }
}

// 使用範例：負數前、非負數後
partition(arr, x -> x < 0);