C 語言演算法：雙指針原地分區，將奇數移至偶數前端

C 語言演算法：雙指針原地分區，將奇數移至偶數前端

給定一個整數陣列，要求原地調整元素順序，使所有奇數位於陣列前半段、偶數位於後半段。此為經典分區問題，可用雙指針單趟掃描 O(N) 解決，空間複雜度 O(1)。

一、 演算法邏輯

• left 從陣列頭向後掃描，尋找偶數（需移至後段）。
• right 從陣列尾向前掃描，尋找奇數（需移至前段）。
• 當 left < right 且左偶右奇時，交換兩者。
• 繼續移動指針，直到相遇。

二、 代碼實現

void adjust_array(int arr[], int size) {
    int left = 0, right = size - 1;
    while (left < right) {
        // 向右移動 left，直到找到偶數或越界
        while (left < right && (arr[left] % 2 == 1)) left++;
        // 向左移動 right，直到找到奇數或越界
        while (left < right && (arr[right] % 2 == 0)) right--;
        if (left < right) {
            int tmp = arr[left];
            arr[left] = arr[right];
            arr[right] = tmp;
            left++; right--; // 可選：交換後繼續縮小範圍
        }
    }
}

三、 測試驗證

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_array(arr, size);
    for (int i = 0; i < size; i++) printf("%d ", arr[i]);
    // 輸出示例：19 3 17 5 15 7 11 13 9 ... (所有奇數在前，順序不保證)
    return 0;
}

四、 關鍵細節

1. 判斷奇偶：x % 2 == 1 為奇，x % 2 == 0 為偶（負數同理，C99 保證 -3 % 2 == -1，建議用 (x & 1) 位運算更高效）。
2. 邊界條件：全奇、全偶、空陣列、單元素，迴圈條件 left < right 天然處理。
3. 不保證相對順序：此演算法不穩定，若需維持奇數間、偶數間原相對順序，需 O(N) 額外空間或 O(N²) 插入法。

五、 變體：三向切分

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

雙指針分區是快速排序 Partition 步驟的核心，也是陣列原地重組的基礎模板，值得熟練掌握。