冒泡排序：用Python實現從小到大排序¶
你有沒有想過，水中的氣泡是怎麼上升的？它們會從水底慢慢往上冒，較大的氣泡會更快到達水面。冒泡排序的名字就來源於這個現象——它會讓數組中較大的元素“冒泡”到數組的末尾。
簡單來說，冒泡排序（Bubble Sort）是一種基礎的排序算法。它的核心思想是：重複地走訪要排序的數組，一次比較兩個相鄰的元素，如果它們的順序錯誤就交換位置，直到整個數組有序。
冒泡排序的工作步驟¶
- 比較相鄰元素：從數組第一個元素開始，依次比較相鄰的兩個元素（比如第1個和第2個，第2個和第3個，…）。
- 交換元素：如果前一個元素比後一個大，就交換它們的位置。
- 重複操作：重複上述步驟，直到所有元素都“冒泡”到正確的位置。每完成一輪，數組末尾的一個最大元素就會被排好序。
- 優化提前終止：如果某一輪中沒有發生任何交換，說明數組已經有序，無需繼續排序。
用Python實現冒泡排序¶
下面通過一個具體例子理解排序過程，並寫出Python代碼。假設我們要排序數組：[64, 34, 25, 12, 22, 11, 90]。
步驟分解（手動模擬）：¶
- 第1輪：比較相鄰元素，最大的數（90）會“冒泡”到末尾，數組變爲：
[34, 25, 12, 22, 11, 64, 90]。 - 第2輪：比較前6個元素，第二大的數（64）會“冒泡”到倒數第二位，數組變爲：
[25, 12, 22, 11, 34, 64, 90]。 - 第3輪：繼續比較，直到所有元素有序。
Python代碼實現：¶
def bubble_sort(arr):
n = len(arr)
# 外層循環控制排序輪數（最多n-1輪）
for i in range(n - 1):
swapped = False # 標記本輪是否發生交換
# 內層循環比較相鄰元素，每輪減少一次比較（末尾已排序）
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
# 交換相鄰元素（Python語法簡化交換）
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
# 如果本輪無交換，說明數組已有序，提前終止
if not swapped:
break
print(f"第{i+1}輪結束：{arr}")
return arr
# 測試
test_arr = [64, 34, 25, 12, 22, 11, 90]
print("原始數組:", test_arr)
sorted_arr = bubble_sort(test_arr)
print("最終排序:", sorted_arr)
代碼解釋：¶
-
外層循環：
for i in range(n - 1)
控制排序輪數，最多需要n-1輪（n爲數組長度），因爲每輪會確定一個最大元素的位置。 -
內層循環：
for j in range(0, n - i - 1)
比較相鄰元素，每輪內層循環的次數比上一輪少1次（因爲末尾i個元素已排好序）。 -
交換邏輯：
arr[j], arr[j + 1] = arr[j + 1], arr[j]
用Python的元組賦值語法，簡潔交換相鄰元素的值。 -
優化標誌：
swapped
如果某輪無交換，說明數組已有序，直接終止循環，避免無效比較。
運行結果（含中間過程）：¶
原始數組: [64, 34, 25, 12, 22, 11, 90]
第1輪結束：[34, 25, 12, 22, 11, 64, 90]
第2輪結束：[25, 12, 22, 11, 34, 64, 90]
第3輪結束：[12, 22, 11, 25, 34, 64, 90]
第4輪結束：[12, 11, 22, 25, 34, 64, 90]
第5輪結束：[11, 12, 22, 25, 34, 64, 90]
最終排序: [11, 12, 22, 25, 34, 64, 90]
冒泡排序的特點¶
- 時間複雜度：最壞情況（完全逆序）爲O(n²)，最好情況（已排序）爲O(n)（優化後）。
- 空間複雜度：O(1)（僅需臨時變量，無額外空間）。
- 穩定性：穩定排序（相等元素相對位置不變）。
總結¶
冒泡排序是最簡單的排序算法之一，核心是“相鄰元素比較與交換”。雖然效率較低（適合小規模數據），但理解其原理對掌握排序思想至關重要。通過Python代碼實現後，你可以輕鬆處理簡單的排序需求，或嘗試優化爲更高效的版本（如歸併排序、快速排序）。
現在，嘗試用其他數組（如[5, 3, 8, 4, 2]）測試冒泡排序，看看是否能正確輸出排序結果吧！