演算法筆記｜泡沫排序法（ Bubble Sort ）

基本概念

  泡沫排序法的概念很簡單，假設有一串數列，分別將相鄰的兩個元素比大小，如果左側的數字較大則交換，經過一個大迴圈後，最大值會跑到最右邊。

  假設有n筆元素，則需比較n-1次迴圈，在一次迴圈中當有n筆資料則需比較n-1次。如下圖，紅字為比較的對象，藍字為比較後是否對調的結果。

圖解泡沫排序法

第1大圈 第1次比較

比較index 0 跟 1 的值，因為8>2則對調

第1大圈 第2次比較

比較index 1 跟 2 的值，因為8>5則對調

第1大圈 第3次比較

比較index 2 跟 3 的值，因為8>1則對調

第1大圈 第4次比較

比較index 3 跟 4 的值，因為8<12則不動

第2大圈 第1次比較

比較index 0 跟 1 的值，因為2<5則不動

第2大圈 第2次比較

比較index 1 跟 2 的值，因為5>1則對調

第2大圈 第3次比較

因為上一輪第一大圈已經確定最右邊為最大值，所以這輪只需要比較3次即可，相信大家已經發現規律了，再來就直接跳到第4大圈第1次比較。

第4大圈 第1次比較

透過泡沫排序法，每一大圈的比較，把最大值換到最右邊，最終可以得到由小排到大的數列。

時間複雜度計算

  第1大圈的比較次數是n-1次，第2大圈是n-2次，第n-1圈的時候是1次，

(n-1)+(n-2)+ ....... +1 = (n^2-n)/2因此時間複雜度為O(n)=n^2。

  泡沫排序法的缺點是如果數列本來就是一個由小排到大的數列時，他仍會把全部的迴圈跑一次，非常的沒有效率，所以建議可以加入一個判斷，若第一圈的比較中沒有任何一個值交換則結束，這樣時間複雜度則減為O(n)=n

泡沫排序法實作

def bubble_sort(arr):
    n = len(arr)
    # 外層迴圈控制回合數
    for i in range(n):
        # 內層迴圈進行比較與交換
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:  # 如果前一個數大於後一個數，則交換
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

# 測資
numbers = [64, 34, 25, 12, 22, 11, 90]
sorted_numbers = bubble_sort(numbers)
print("排序後的結果：", sorted_numbers)