C# 標準冒泡排序實現：優化版含提前終止檢測

算法核心

冒泡排序通過相鄰元素比較交換，將大元素逐步「冒泡」到數組末端。優化點：若某輪未發生交換，說明已有序，提前終止。

標準實現

public void BubbleSort(int[] R)
{
    int n = R.Length;
    for (int i = 0; i < n - 1; i++)
    {
        bool exchanged = false;
        // 每輪將最大值推到 n-1-i 位置
        for (int j = n - 2; j >= i; j--)
        {
            if (R[j + 1] < R[j])
            {
                int temp = R[j + 1];
                R[j + 1] = R[j];
                R[j] = temp;
                exchanged = true;
            }
        }
        if (!exchanged) break; // 本輪無交換，已有序
    }
}

關鍵點解析

複雜度分析

• 時間：最差 O(n²)，最佳 O(n)（已有序），平均 O(n²)
• 空間：O(1) 原地排序
• 穩定性：穩定（相等元素不交換）

測試用例

int[] arr = { 64, 34, 25, 12, 22, 11, 90 };
BubbleSort(arr);
// 結果: 11, 12, 22, 25, 34, 64, 90

int[] sorted = { 1, 2, 3, 4, 5 };
BubbleSort(sorted); // 單輪檢測後即 break，極快

面試提示

• 能手寫正確邊界條件（j >= i 而非 j > i）
• 說明優化原理與最佳/最差情況
• 對比插入排序、快速排序優劣