冒泡排序

5.1 冒泡排序的定義

冒泡排序 (Bubble Sort) 是一種簡單的排序演算法，它反覆穿過列表，依次比較相鄰的元素，如果它們的順序錯誤，就交換它們的位置。這個過程會一直重複，直到列表完全排序好為止。

原理：

1. 演算法穿過列表並比較每對相鄰的元素。
2. 如果元素順序錯誤（第一個比第二個大，對於升序排序）— 它們會被交換。
3. 這一過程對列表中的所有元素對重複。
4. 每次完整地通過列表後，最大的元素會「浮動」到它的正確位置（就像水面上的氣泡），所以它將不會參加接下來的排序。
5. 過程會一直重複，直到列表排序完成。

冒泡排序的時間和空間複雜度

時間複雜度：

• 最壞情況: O(n^2) — 在元素最初按照相反順序排列時會發生。
• 平均情況: O(n^2) — 在元素隨機排列時會發生。
• 最佳情況: O(n) — 在元素已經排序時發生（演算法可以為這種情況優化，加入一個檢查來判斷此通過是否發生了元素交換）。

空間複雜度：

O(1) — 因為演算法使用了恆定量的額外記憶體（僅用於存儲幾個臨時值的變數）。

5.2 演算法的實現

「冒泡排序」演算法是最簡單且原始的排序演算法。它只是簡單地兩兩比較元素並在需要時交換它們的位置。

版本 1：

array = [6, 43, 2, 1, 2, 1, 1, 1, 1, 6, 7, 8]
n = len(array)
            
for i in range(n):
    for j in range(n - 1): if array[j] > array[j + 1]: array[j], array[j + 1] = array[j + 1], array[j]  # 交換元素

print("排序後的陣列:", array)
# 輸出: 排序後的陣列: [1, 1, 1, 1, 1, 2, 2, 6, 6, 7, 8, 43]

內部循環（以綠色顯示）比較元素與其右邊的相鄰元素。如果需要就交換它們的位置。

版本 2：

我們可以在演算法中立即增加一個優化：第一遍通過後，最右邊的元素是最大的，所以在下一次循環時可以不用考慮它。

第二次遍歷後右邊會有2個最大的元素，所以內部循環可以不必進行到 n - 1，而是到 n - 1 - i。其中 i 是外部循環已經進行的迭代次數。

新的變化會看起來是這樣的：

array = [6, 43, 2, 1, 2, 1, 1, 1, 1, 6, 7, 8]
n = len(array)
            
for i in range(n):
    for j in range(n - 1 - i): if array[j] > array[j + 1]: array[j], array[j + 1] = array[j + 1], array[j]  # 交換元素

print("排序後的陣列:", array)
# 輸出: 排序後的陣列: [1, 1, 1, 1, 1, 2, 2, 6, 6, 7, 8, 43]

版本 3：

同時，陣列可能已經幾乎排序好。所以我們可以增加一個優化：如果內循環完成了所有元素，但沒有進行任何交換，那麼排序就完成了。

在這個版本中使用了變量 swapped，用以追蹤最後一次遍歷中是否發生了元素交換。如果在遍歷陣列後沒有發生任何交換，這意味著陣列已經是排序好的，並且進一步的迭代是沒有意義的 — 因為它們不會改善排序。因此，變量 swapped 可以大大加快演算法在幾乎已排序的陣列上的作用，提前結束其執行。

Python 中冒泡排序的實現：

def bubble_sort(array):
    n = len(array)
    for i in range(n):
        swapped = False # 優化：檢查是否有交換發生
        for j in range(0, n - i - 1): if array[j] > array[j + 1]: array[j], array[j + 1] = array[j + 1], array[j]  # 交換元素
                swapped = True
        if not swapped:
            break  # 如果沒有交換，陣列已經排序好
    return array

# 使用範例：
array = [64, 34, 25, 12, 22, 11, 90]
sorted_array = bubble_sort(array)
print("排序後的陣列:", sorted_array)
# 輸出: 排序後的陣列: [11, 12, 22, 25, 34, 64, 90]