什麼是排序？¶
在我們生活中，排序是很常見的操作。比如考試成績排名、手機通訊錄按字母排序、字典裏按字母順序查單詞……本質上，排序就是將一組無序的數據，按照特定規則（比如從小到大、從大到小）重新排列的過程。在計算機科學中，排序算法是最基礎也最核心的算法之一，掌握排序算法能幫助我們更高效地處理數據。
什麼是冒泡排序？¶
冒泡排序（Bubble Sort）是最簡單的排序算法之一，它的名字來源於“氣泡”——就像水中的氣泡會向上浮一樣，冒泡排序中較大的元素會通過交換逐漸“冒”到數組的末尾。
舉個例子：如果有一組數字 [5, 3, 8, 4, 2]，我們要將它們從小到大排序。冒泡排序的過程就像這樣：每一輪都會把當前未排序部分的“最大氣泡”（最大元素）“推”到末尾，直到所有元素都排好序。
冒泡排序的核心思路¶
以 [5, 3, 8, 4, 2] 爲例，逐步拆解冒泡過程：
第一輪（確定最大元素）¶
從第一個元素開始，依次比較相鄰的兩個元素，如果前一個比後一個大，就交換它們的位置：
- 比較 5 和 3：5 > 3，交換 → [3, 5, 8, 4, 2]
- 比較 5 和 8：5 < 8，不交換
- 比較 8 和 4：8 > 4，交換 → [3, 5, 4, 8, 2]
- 比較 8 和 2：8 > 2，交換 → [3, 5, 4, 2, 8]
結果：最大元素 8 已經“冒”到了末尾，現在未排序部分是 [3, 5, 4, 2]。
第二輪（確定第二大元素）¶
未排序部分長度減1（去掉末尾的 8），繼續比較相鄰元素：
- 比較 3 和 5：3 < 5，不交換
- 比較 5 和 4：5 > 4，交換 → [3, 4, 5, 2]
- 比較 5 和 2：5 > 2，交換 → [3, 4, 2, 5]
結果：第二大元素 5 已“冒”到倒數第二位置，未排序部分是 [3, 4, 2]。
第三輪（確定第三大元素）¶
未排序部分長度繼續減1，繼續比較：
- 比較 3 和 4：3 < 4，不交換
- 比較 4 和 2：4 > 2，交換 → [3, 2, 4]
結果：第三大元素 4 已“冒”到倒數第三位置，未排序部分是 [3, 2]。
第四輪（確定第四大元素）¶
未排序部分僅剩兩個元素：
- 比較 3 和 2：3 > 2，交換 → [2, 3]
結果：所有元素排序完成，最終數組爲 [2, 3, 4, 5, 8]。
冒泡排序的步驟總結¶
- 外層循環：控制需要進行多少輪比較。數組長度爲
n時，最多需要n-1輪（因爲每輪確定一個元素的位置）。 - 內層循環：每輪比較相鄰元素，將較大的元素“冒泡”到末尾。每輪結束後，未排序部分長度減1（即不需要再比較已排好序的末尾元素）。
- 優化點：如果某一輪沒有發生交換，說明數組已排好序，可提前終止循環（避免無效計算）。
代碼實現（Python）¶
基礎版本（無優化）¶
def bubble_sort(arr):
n = len(arr)
for i in range(n - 1): # 外層循環：共n-1輪
for j in range(n - 1 - i): # 內層循環：每輪比較n-1-i次
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j] # 交換相鄰元素
return arr
# 測試
arr = [5, 3, 8, 4, 2]
print(bubble_sort(arr)) # 輸出：[2, 3, 4, 5, 8]
優化版本（提前終止）¶
def optimized_bubble_sort(arr):
n = len(arr)
for i in range(n - 1):
swapped = False # 標記是否發生交換
for j in range(n - 1 - i):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
if not swapped: # 若本輪無交換，直接結束
break
return arr
# 測試（對已排序數組優化明顯）
arr = [1, 2, 3, 4, 5]
print(optimized_bubble_sort(arr)) # 輸出：[1, 2, 3, 4, 5]（僅需1輪即可結束）
冒泡排序的複雜度分析¶
- 時間複雜度：
- 最壞情況（完全逆序）：每輪都需交換，共需
n-1 + n-2 + ... + 1 = n(n-1)/2次比較，時間複雜度爲 O(n²)。 -
最好情況（已排序）：優化版本僅需1輪（無交換），時間複雜度爲 O(n)。
-
空間複雜度：僅需常數級額外空間（交換時的臨時變量），空間複雜度爲 O(1)（原地排序）。
冒泡排序的特點與適用場景¶
- 優點：簡單易懂，實現容易，適合理解排序算法的基本思想。
- 缺點：效率較低（O(n²)），數據量大時不適用。
- 適用場景：數據量小或對效率要求不高的場景（如教學演示、簡單數據排序）。
小練習¶
嘗試用冒泡排序對數組 [9, 7, 6, 15, 16, 5, 10, 11] 排序，你能手動走一遍流程嗎？可以參考上述步驟，寫出代碼驗證結果。
通過以上講解，相信你已經掌握了冒泡排序的核心邏輯。作爲最基礎的排序算法，冒泡排序能幫助你理解“比較交換”的思想，爲學習更復雜的排序算法（如快速排序、歸併排序）打下基礎！