C語言陣列奇偶排序：額外空間法 vs 原地冒泡法 (空間換時間)

題目

將陣列調整為「所有奇數在前，偶數在後」，順序不限。

方法一：額外空間 O(n) 時間 O(n) 空間

void odd_even_extra(int *arr, int n) {
    int *odd = malloc(n * sizeof(int));
    int *even = malloc(n * sizeof(int));
    int o = 0, e = 0;
    for (int i = 0; i < n; 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);
}

• 穩定 (保持相對順序)、簡單、快。
• 缺點：需額外記憶體，大陣列可能 OOM。

方法二：原地雙指針 (類快排 partition) O(n) 時間 O(1) 空間

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

• 單趟掃描、原地交換、空間最優。
• 不穩定 (相對順序改變)。

方法三：冒泡思路 O(n²) 時間 O(1) 空間 (原碼)

// 將偶數像氣泡往右推
for (int i = 0; i < n; i++)
    for (int j = 0; j < n - i - 1; j++)
        if ((arr[j] & 1) == 0) // arr[j] 是偶數
            swap(&arr[j], &arr[j+1]);

• 教學示範冒泡思想，實戰**極不推薦** (大陣列效能災難)。

總結選型