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

## 演算法筆記｜泡沫排序法（ Bubble Sort ） ### 基本概念 &emsp;&emsp;泡沫排序法的概念很簡單，假設有一串數列，分別將相鄰的兩個元素比大小，如果左側的數字較大則交換，經過一個大迴圈後，最大值會跑到最右邊。 &emsp;&emsp;假設有n筆元素，則需比較n-1次迴圈，在一次迴圈中當有n筆資料則需比較n-1次。如下圖，紅字為比較的對象，藍字為比較後是否對調的結果。 ### 圖解泡沫排序法 **第1大圈** 第1次比較 | 索引 index | 0 | 1 | 2 | 3 | 4 | | ---------- | --- | --- | --- | --- | --- | | 值 value | 8 | 2 | 5 | 1 | 12 | 比較index 0 跟 1 的值，因為8>2則**對調** | 索引 index | 0 | 1 | 2 | 3 | 4 | | ---------- | --- | --- | --- | --- | --- | | 值 value | 2 | 8 | 5 | 1 | 12 | **第1大圈** 第2次比較 | 索引 index | 0 | 1 | 2 | 3 | 4 | | ---------- | --- | --- | --- | --- | --- | | 值 value | 2 | 8 | 5 | 1 | 12 | 比較index 1 跟 2 的值，因為8>5則**對調** | 索引 index | 0 | 1 | 2 | 3 | 4 | | ---------- | --- | --- | --- | --- | --- | | 值 value | 2 | 5 | 8 | 1 | 12 | **第1大圈** 第3次比較 | 索引 index | 0 | 1 | 2 | 3 | 4 | | ---------- | --- | --- | --- | --- | --- | | 值 value | 2 | 5 | 8 | 1 | 12 | 比較index 2 跟 3 的值，因為8>1則**對調** | 索引 index | 0 | 1 | 2 | 3 | 4 | | ---------- | --- | --- | --- | --- | --- | | 值 value | 2 | 5 | 1 | 8 | 12 | **第1大圈** 第4次比較 | 索引 index | 0 | 1 | 2 | 3 | 4 | | ---------- | --- | --- | --- | --- | --- | | 值 value | 2 | 5 | 1 | 8 | 12 | 比較index 3 跟 4 的值，因為8<12則**不動** | 索引 index | 0 | 1 | 2 | 3 | 4 | | ---------- | --- | --- | --- | --- | --- | | 值 value | 2 | 5 | 1 | 8 | 12 | **第2大圈** 第1次比較 | 索引 index | 0 | 1 | 2 | 3 | 4 | | ---------- | --- | --- | --- | --- | --- | | 值 value | 2 | 5 | 1 | 8 | 12 | 比較index 0 跟 1 的值，因為2<5則**不動** | 索引 index | 0 | 1 | 2 | 3 | 4 | | ---------- | --- | --- | --- | --- | --- | | 值 value | 2 | 5 | 1 | 8 | 12| **第2大圈** 第2次比較 | 索引 index | 0 | 1 | 2 | 3 | 4 | | ---------- | --- | --- | --- | --- | --- | | 值 value | 2 | 5 | 1 | 8 | 12 | 比較index 1 跟 2 的值，因為5>1則**對調** | 索引 index | 0 | 1 | 2 | 3 | 4 | | ---------- | --- | --- | --- | --- | --- | | 值 value | 2 | 1 | 5 | 8 | 12| **第2大圈** 第3次比較 | 索引 index | 0 | 1 | 2 | 3 | 4 | | ---------- | --- | --- | --- | --- | --- | | 值 value | 2 | 1 | 5 | 8 | 12 | | 索引 index | 0 | 1 | 2 | 3 | 4 | | ---------- | --- | --- | --- | --- | --- | | 值 value | 2 | 1 | 5 | 8 | 12 | &emsp;&emsp;因為上一輪第一大圈已經確定最右邊為最大值，所以這輪只需要比較3次即可，相信大家已經發現規律了，再來就直接跳到第4大圈第1次比較。 **第4大圈** 第1次比較 | 索引 index | 0 | 1 | 2 | 3 | 4 | | ---------- | --- | --- | --- | --- | --- | | 值 value | 1 | 2 | 5 | 8 | 12 | | 索引 index | 0 | 1 | 2 | 3 | 4 | | ---------- | --- | --- | --- | --- | --- | | 值 value | 1 | 2 | 5 | 8 | 12 | &emsp;&emsp;透過泡沫排序法，每一大圈的比較，把最大值換到最右邊，最終可以得到由小排到大的數列。 ### 時間複雜度計算 &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$ | ### 泡沫排序法實作 ``` 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) ```