C# 排序演算法實作：氣泡排序

氣泡排序是最基礎的排序演算法之一，透過相鄰元素兩兩比較並交換，將較大 (或較小) 的元素像氣泡一樣逐步「浮」到陣列末端。雖然時間複雜度為 O(n²)，但其原理直觀，適合教學入門與極小資料集。

演算法原理

1. 外層迴圈控制排序趟數 (最多 n-1 趟)。
2. 內層迴圈從陣列末端向前掃描，比較相鄰元素 arr[j] 與 arr[j-1]。
3. 若順序錯誤則交換，並設定旗標 swapped = true。
4. 若某趟掃描未發生任何交換，代表陣列已有序，提前終止。

C# 實作程式碼 (含優化旗標)

public class BubbleSorter
{
    public void Sort(int[] arr)
    {
        for (int i = 1; i < arr.Length; i++)
        {
            bool swapped = false;
            for (int j = arr.Length - 1; j >= i; j--)
            {
                if (arr[j] < arr[j - 1])
                {
                    int tmp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = tmp;
                    swapped = true;
                }
            }
            if (!swapped) return; // 提前終止優化
        }
    }
}

// 測試
static void Main()
{
    int[] data = { 1, 5, 11, 6, 4, 21, 99, 2, 15, 11, 34, 0, 33, 47 };
    var sorter = new BubbleSorter();
    sorter.Sort(data);
    Console.WriteLine("氣泡排序結果：" + string.Join(" ", data));
}

複雜度分析

優缺點與適用場景

• 優點：程式碼極簡單、穩定排序、可提前終止、無額外記憶體。
• 缺點：平均/最差 O(n²)、交換次數多、緩存局部性差。
• 適用：教學、資料量極小 (n < 20)、近乎有序資料、嵌入式系統記憶體極度受限。

常見變體

• 雞尾酒排序：雙向氣泡排序，減少「烏龜」 (小數值在右側) 移動緩慢問題。
• 梳排序：引入間距因子，類似 Shell Sort 思想。

實務建議

生產環境**絕不**手寫氣泡排序。請使用 Array.Sort / List<T>.Sort (Introspective Sort)。理解氣泡排序有助於建立演算法分析基礎 (最佳/平均/最差情況、穩定性、原地排序等概念)。