C 語言經典氣泡排序法實作與優化

標準氣泡排序

void BubbleSort(int *array, int len) {
    bool swapped = true;
    do {
        swapped = false;
        for (int i = 0; i < len - 1; i++) {
            if (array[i] > array[i+1]) {
                int tmp = array[i];
                array[i] = array[i+1];
                array[i+1] = tmp;
                swapped = true;
            }
        }
    } while (swapped);
}

運作原理

• 相鄰元素兩兩比較，大者後移，每輪將最大值「浮」到陣列尾端。
• 若某輪未發生任何交換 (swapped == false)，表示已有序，提前結束。

複雜度分析

進階優化版：雙向氣泡排序

void CocktailSort(int *a, int n) {
    int left = 0, right = n - 1;
    while (left < right) {
        // 正向：大者右移
        for (int i = left; i < right; i++)
            if (a[i] > a[i+1]) { SWAP(a[i], a[i+1]); }
        right--;
        // 反向：小者左移
        for (int i = right; i > left; i--)
            if (a[i] < a[i-1]) { SWAP(a[i], a[i-1]); }
        left++;
    }
}

又稱「雞尾酒排序」，可同時將極大值移至右端、極小值移至左端，減少輪數約一半。

適用場景

• 資料量極小 (n < 50)。
• 資料近乎有序 (最佳 O(n))。
• 教學示範、嵌入式系統記憶體極度受限。

總結

氣泡排序雖非高效通用排序，但邏輯簡單、原地排序、穩定，且透過「提前結束」與「雙向掃描」優化後，在特定場景仍具實用價值。