---
# System prepended metadata

title: 演算法筆記｜泡沫排序法（ Bubble Sort ）
tags: [演算法]

---

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

### 基本概念

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


&emsp;&emsp;假設有<font color="#f00">n</font>筆元素，則需比較<font color="#f00">n-1</font>次迴圈，在一次迴圈中當有<font color="#f00">n</font>筆資料則需比較<font color="#f00">n-1</font>次。如下圖，<font color="#f00">紅字為比較的對象</font>，<font color="#0000FF">藍字為比較後是否對調的結果</font>。

<br/>

### 圖解泡沫排序法

**第1大圈** 第1次比較
| 索引 index | 0   | 1   | 2   | 3   | 4   |
| ---------- | --- | --- | --- | --- | --- |
| 值 value   | <font color="#f00">8</font>  | <font color="#f00">2</font>    | 5   | 1   | 12   |

比較index 0 跟 1 的值，因為8>2則**對調**
| 索引 index | 0   | 1   | 2   | 3   | 4   |
| ---------- | --- | --- | --- | --- | --- |
| 值 value   | <font color="#0000FF">2</font>  | <font color="#0000FF">8</font>    | 5   | 1   | 12   |


**第1大圈** 第2次比較

| 索引 index | 0   | 1   | 2   | 3   | 4   |
| ---------- | --- | --- | --- | --- | --- |
| 值 value   | 2  | <font color="#f00">8</font>    | <font color="#f00">5</font>   | 1   | 12   |

比較index 1 跟 2 的值，因為8>5則**對調**
| 索引 index | 0   | 1   | 2   | 3   | 4   |
| ---------- | --- | --- | --- | --- | --- |
| 值 value   | 2  | <font color="#0000FF">5</font>    | <font color="#0000FF">8</font>   | 1   | 12   |

**第1大圈** 第3次比較

| 索引 index | 0   | 1   | 2   | 3   | 4   |
| ---------- | --- | --- | --- | --- | --- |
| 值 value   | 2  |  5   | <font color="#f00">8</font>   | <font color="#f00">1</font>   | 12   |

比較index 2 跟 3 的值，因為8>1則**對調**
| 索引 index | 0   | 1   | 2   | 3   | 4   |
| ---------- | --- | --- | --- | --- | --- |
| 值 value   | 2  | 5   | <font color="#0000FF">1</font>   | <font color="#0000FF">8</font>   | 12   |

**第1大圈** 第4次比較

| 索引 index | 0   | 1   | 2   | 3   | 4   |
| ---------- | --- | --- | --- | --- | --- |
| 值 value   | 2  |  5   | 1   | <font color="#f00">8</font>   | <font color="#f00">12</font>   |

比較index 3 跟 4 的值，因為8<12則**不動**
| 索引 index | 0   | 1   | 2   | 3   | 4   |
| ---------- | --- | --- | --- | --- | --- |
| 值 value   | 2  | 5   | 1   | <font color="#0000FF">8</font>   | <font color="#0000FF">12</font>   |



**第2大圈** 第1次比較

| 索引 index | 0   | 1   | 2   | 3   | 4   |
| ---------- | --- | --- | --- | --- | --- |
| 值 value   | <font color="#f00">2</font>  |  <font color="#f00">5</font>  | 1   | 8   | 12   |

比較index 0 跟 1 的值，因為2<5則**不動**
| 索引 index | 0   | 1   | 2   | 3   | 4   |
| ---------- | --- | --- | --- | --- | --- |
| 值 value   | <font color="#0000FF">2</font>  | <font color="#0000FF">5</font>      | 1   | 8   | 12|

**第2大圈** 第2次比較

| 索引 index | 0   | 1   | 2   | 3   | 4   |
| ---------- | --- | --- | --- | --- | --- |
| 值 value   | 2  |  <font color="#f00">5</font>  | <font color="#f00">1</font>   | 8   | 12   |

比較index 1 跟 2 的值，因為5>1則**對調**
| 索引 index | 0   | 1   | 2   | 3   | 4   |
| ---------- | --- | --- | --- | --- | --- |
| 值 value   | 2  | <font color="#0000FF">1</font>      | <font color="#0000FF">5</font>   | 8   | 12|

**第2大圈** 第3次比較

| 索引 index | 0   | 1   | 2   | 3   | 4   |
| ---------- | --- | --- | --- | --- | --- |
| 值 value   | 2  |  1  | <font color="#f00">5</font>   | <font color="#f00">8</font>   | 12   |

| 索引 index | 0   | 1   | 2   | 3   | 4   |
| ---------- | --- | --- | --- | --- | --- |
| 值 value   | 2  |  1  | <font color="#0000FF">5</font>   | <font color="#0000FF">8</font>   | 12   |

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

**第4大圈** 第1次比較

| 索引 index | 0   | 1   | 2   | 3   | 4   |
| ---------- | --- | --- | --- | --- | --- |
| 值 value   | <font color="#f00">1</font>  |  <font color="#f00">2</font>  | 5   | 8   | 12   |

| 索引 index | 0   | 1   | 2   | 3   | 4   |
| ---------- | --- | --- | --- | --- | --- |
| 值 value   | <font color="#0000FF">1</font>  |  <font color="#0000FF">2</font>  | 5   | 8   | 12   |

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

<br/>

### 時間複雜度計算

&emsp;&emsp;第1大圈的比較次數是n-1次，第2大圈是n-2次，第n-1圈的時候是1次，
$(n-1)+(n-2)+ ....... +1 = (n^2-n)/2$，因此時間複雜度為 $O(n)=n^2$ 。

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



|  | 最佳解   | 平均解     |  最差解   |
| -------- | -------- | ---------- | --- |
| 時間複雜度     | $O(n)=n$ | $O(n)=n^2$ |  $O(n)=n^2$   |

<br/>

### 泡沫排序法實作

```
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)

```


