由後而前依序將兩兩相鄰的值互相比較，直到所有的值都被排到正確的位置為止。

  • 最壞情況 (Worst Case): O(n²)
    • 當數組完全逆序時（如 [5,4,3,2,1]）
    • 外層循環需要執行 n-1 次
    • 內層循環每次需要執行 n-i-1 次
    • 總比較次數：(n-1) + (n-2) + … + 1 = n(n-1)/2
    • 所以是 O(n²)
  • 最好情況 (Best Case): O(n)
    • 當數組已經排好序時（如 [1,2,3,4,5]）
    • 只需要執行一次外層循環
    • 內層循環執行 n-1 次比較
    • 由於沒有發生交換，會提前退出
    • 所以是 O(n)
  • 平均情況 (Average Case): O(n²)
    • 在隨機數據的情況下
    • 仍然需要進行大量的比較和交換
    • 複雜度接近最壞情況

圖示

現假設有一陣列 [6,5,4,9,1]，要透過氣泡排序將陣列由小排到大的過程如下：

image.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
static void BubbleSort(int[] arr)
{
    int n = arr.Length;
    
    // Outer loop - each pass reduces the unsorted portion by 1
    for (int i = 0; i < n - 1; i++)
    {
        // Flag to optimize - if no swaps occur, array is sorted
        bool swapped = false;
        
        // Inner loop - compare adjacent elements
        for (int j = 0; j < n - i - 1; j++)
        {
            // If current element is greater than next element, swap them
            if (arr[j] > arr[j + 1])
            {
                // Swap elements
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = true;
            }
        }
        
        // If no swapping occurred, array is already sorted
        if (!swapped)
            break;
    }
}