C語言雙指針原地調整陣列：奇數前偶數後 (最優解法)

標準 Partition 算法 (快排核心邏輯)

#include 
#include 

void odd_before_even(int *arr, int len) {
    assert(arr);
    int left = 0, right = len - 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--;
        }
    }
}

int main() {
    int arr[] = {1,2,3,4,5};
    int len = sizeof(arr)/sizeof(arr[0]);
    odd_before_even(arr, len);
    for (int i = 0; i < len; i++) printf("%d ", arr[i]);
    // 輸出範例: 1 5 3 4 2 (奇數在前，順序可能變)
    return 0;
}

關鍵點

1. arr[left] & 1 判斷奇數 (1)，!(arr[right] & 1) 判斷偶數 (0)。
2. 雙指針向中間收斂，單趟 O(n)、原地 O(1)。
3. 交換後 left++, right-- 避免死循環。
4. 不保證穩定性 (相對順序會變)。

變體：保持穩定順序 (O(n) 時間 O(n) 空間)

見上一篇方法一 (額外空間法)。