C 語言實現陣列奇偶排序：額外空間法 vs 冒泡法優化對比

C 語言實現陣列奇偶排序：額外空間法 vs 冒泡法優化對比

「奇偶排序」指將陣列重組為「所有奇數在前，所有偶數在後」。本文對比兩種實現：額外空間法（穩定、O(N)）與冒泡法（原地、O(N²)），分析時空權衡。

一、 方法一：額外空間法（推薦一般場景）

分配兩個暫存陣列分別收集奇數與偶數，再合併回原陣列。

void odd_even_sort_extra(int arr[], int len) {
    int *odd = malloc(len * sizeof(int));
    int *even = malloc(len * sizeof(int));
    int o = 0, e = 0;
    for (int i = 0; i < len; i++) {
        if (arr[i] & 1) odd[o++] = arr[i];
        else even[e++] = arr[i];
    }
    memcpy(arr, odd, o * sizeof(int));
    memcpy(arr + o, even, e * sizeof(int));
    free(odd); free(even);
}

• 優點：時間 O(N)、穩定（保持奇數/偶數內部相對順序）、邏輯簡單。
• 缺點：需 O(N) 額外空間。

二、 方法二：冒泡法原地重組（不推薦大數據）

利用冒泡排序思想，將偶數像氣泡一樣「浮」到後端。

void odd_even_sort_bubble(int arr[], int len) {
    for (int i = 0; i < len - 1; i++) {
        int swapped = 0;
        for (int j = 0; j < len - 1 - i; j++) {
            if ((arr[j] % 2 == 0) && (arr[j+1] % 2 == 1)) { // 前偶後奇，交換
                int tmp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = tmp;
                swapped = 1;
            }
        }
        if (!swapped) break; // 優化：提前結束
    }
}

• 優點：原地操作，O(1) 空間。
• 缺點：時間 O(N²)，大陣列極慢；不穩定（相同奇偶元素相對順序可能改變）。

三、 性能對比表

四、 最佳實踐建議

1. 優先用額外空間法：現代系統記憶體充足，O(N) 時間優勢壓倒性。
2. 若嚴禁額外空間：改用雙指針分區法（上文 adjust_array），O(N) 時間、O(1) 空間、但不穩定。
3. 避免冒泡法：除非陣列極小（< 50）且極度缺記憶體，否則性能不可接受。

選擇演算法本質是時空權衡，理解各法優劣，方能因地制宜。