C 語言雙指針原地分區：調整陣列使奇數前置、偶數後置

C 語言雙指針原地分區：調整陣列使奇數前置、偶數後置

給定整數陣列，要求原地重組使所有奇數位於前半段、偶數位於後半段。雙指針單趟掃描 O(N)、O(1) 空間，是最優解法。

一、 演算法步驟

1. left = 0，right = size-1。
2. left 右移找偶數（需換到後段）；right 左移找奇數（需換到前段）。
3. 若 left < right 且左偶右奇，交換。
4. 重複直到指針相遇。

二、 代碼實現

void adjust_arr(int arr[], int size) {
    int left = 0, right = size - 1;
    while (left < right) {
        while (left < right && (arr[left] & 1)) left++;   // 奇數跳過
        while (left < right && !(arr[right] & 1)) right--; // 偶數跳過
        if (left < right) {
            int tmp = arr[left];
            arr[left] = arr[right];
            arr[right] = tmp;
            left++; right--;
        }
    }
}

使用位運算 x & 1 判斷奇偶，比取模更高效。

三、 測試案例

int main() {
    int arr[] = {2,3,4,5,6,7,10,11,12,13,14,15,16,8,9,17,18,19,20};
    int size = sizeof(arr)/sizeof(arr[0]);
    adjust_arr(arr, size);
    for (int i=0; i<size; i++) printf("%d ", arr[i]);
    // 輸出：19 3 17 5 15 7 11 13 9 ... (奇數在前，順序不保證)
    return 0;
}

四、 關鍵細節

• 不穩定：相對順序不保留。若需穩定，需 O(N) 額外空間或 O(N²) 插入法。
• 邊界安全：left < right 迴圈條件天然處理空陣列、全奇、全偶。
• 負數處理：C99 規定 -3 % 2 == -1，x & 1 對負數同樣正確（補碼最低位 1 為奇）。

五、 擴展：三向切分

若需分為 <k、==k、>k 三段，參考 Dutch National Flag 演算法（三指針單趟）。