在計算機科學中，排序算法是將一組數據按照特定順序（通常是升序或降序）重新排列的過程。我們生活中經常需要排序，比如手機相冊按日期排序照片，購物清單按字母排序商品，這些背後都是排序算法在發揮作用。而冒泡排序（Bubble Sort）是最簡單的排序算法之一，它的核心思想就像水中的氣泡一樣——大的元素會“冒”到數組的末尾。
一、冒泡排序的基本思想¶
想象一下，你有一堆大小不一的石子，需要把它們按從小到大排列。冒泡排序的思路是：從數組的第一個元素開始，依次比較相鄰的兩個元素，如果前一個比後一個大，就交換它們的位置。經過一輪比較後，最大的元素會“冒泡”到數組的最後一位；接着對剩下的元素重複這個過程，直到所有元素都排好序。
舉個例子：要排序數組 [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，已排好。 -
第二輪：對前4個元素
[3, 5, 4, 2]重複比較，把第二大的數推到倒數第二位。 - 3 和 5 比較：3 < 5，不交換
- 5 和 4 比較：5 > 4，交換 →
[3, 4, 5, 2, 8] - 5 和 2 比較：5 > 2，交換 →
[3, 4, 2, 5, 8] -
此時數組倒數第二位是第二大的數
5，已排好。 -
第三輪：對前3個元素
[3, 4, 2]重複比較，把第三大的數推到倒數第三位。 - 3 和 4 比較：3 < 4，不交換
- 4 和 2 比較：4 > 2，交換 →
[3, 2, 4, 5, 8] -
此時數組倒數第三位是第三大的數
4，已排好。 -
第四輪：對前2個元素
[3, 2]比較，把第四大的數推到倒數第四位。 - 3 和 2 比較：3 > 2，交換 →
[2, 3, 4, 5, 8] - 此時數組已完全有序，排序結束。
二、冒泡排序的步驟詳解¶
冒泡排序的核心步驟可以總結爲以下幾點：
- 確定數組長度：假設數組爲
arr，長度爲n。 - 外層循環控制輪數：需要進行
n-1輪比較（因爲每輪確定一個元素的位置，最後一個元素自然有序）。 - 內層循環比較相鄰元素：每輪中，從第一個元素開始，依次比較相鄰元素（
arr[j]和arr[j+1]），如果arr[j] > arr[j+1]，則交換位置。 - 優化提前終止：如果某一輪沒有發生任何交換，說明數組已完全有序，可提前結束排序。
三、代碼示例（Python）¶
下面用 Python 實現冒泡排序，並結合示例數組驗證效果。代碼分爲兩步：定義排序函數，以及測試排序效果。
def bubble_sort(arr):
n = len(arr)
# 外層循環控制輪數（最多n-1輪）
for i in range(n - 1):
swapped = False # 標記本輪是否有交換
# 內層循環比較相鄰元素，每輪減少一次比較（最後i個元素已排好序）
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
# 測試冒泡排序
test_arr = [5, 3, 8, 4, 2]
print("排序前：", test_arr)
sorted_arr = bubble_sort(test_arr)
print("排序後：", sorted_arr)
輸出結果：
排序前： [5, 3, 8, 4, 2]
排序後： [2, 3, 4, 5, 8]
四、冒泡排序的優化與複雜度分析¶
- 優化提前終止：通過
swapped標記，如果某一輪沒有交換，直接跳出循環，避免不必要的比較。 - 時間複雜度：
- 最壞情況（完全逆序）：需要n-1 + n-2 + ... + 1 = n(n-1)/2 ≈ O(n²)次比較和交換。
- 最好情況（已排序）：僅需一輪比較（無交換），時間複雜度O(n)。 - 空間複雜度：僅需要常數級額外空間（交換元素），因此空間複雜度
O(1)。
五、總結¶
冒泡排序是最簡單的排序算法之一，核心思想是通過重複交換相鄰元素，將大元素“冒泡”到末尾。它的優點是實現簡單、易於理解，缺點是時間複雜度較高，適合小規模數據排序。如果你剛開始學習排序算法，冒泡排序是非常好的入門選擇，能幫助你理解排序的基本邏輯！