泡沫排序法教學：原理、程式碼與時間複雜度

用白話說明原理

比較前兩個元素。如果第一個比較大，就交換它們。接著比較第二個和第三個，再比較第三個和第四個，依此類推直到串列結尾。這就是一回合（pass）。第一回合結束後，最大的元素必定在最後，因為每次比較都把它往右帶了一步。

對尚未排序的部分重複進行這一回合，未排序的部分每次會少一個元素。如果整個回合都沒有發生交換，串列就已排序完成，可以提早結束。

逐回合範例

將 [5, 1, 4, 2, 8] 由小到大排序。直線之後的元素已在最終位置。

沒有提早結束的機制時，演算法會再跑第四回合；有的話，這裡三回合就夠了。

Python 實作

def bubble_sort(items):
    """Sort a list in place, ascending. Returns the same list."""
    n = len(items)
    for end in range(n - 1, 0, -1):     # last index of the unsorted part
        swapped = False
        for i in range(end):
            if items[i] > items[i + 1]:  # strict >, keeps equal items in order
                items[i], items[i + 1] = items[i + 1], items[i]
                swapped = True
        if not swapped:                  # no swaps: already sorted
            break
    return items
print(bubble_sort([5, 1, 4, 2, 8]))     # [1, 2, 4, 5, 8]
print(bubble_sort([3, 3, 1]))           # [1, 3, 3]
print(bubble_sort([]))                  # []

內層迴圈在 end 就停止，因為其後的元素都已就定位。swapped 旗標讓已排序的輸入有 O(n) 的最佳情況。

時間與空間複雜度

對 10,000 個反向排列的元素，這是將近 5,000 萬次比較與交換。交換次數永遠等於逆序對（順序顛倒的元素對）的數量。

泡沫排序與其他排序法的比較

泡沫排序是穩定的，因為它只交換相鄰元素，而且只在嚴格逆序時才交換，所以相等的元素不會互相越過。插入排序的複雜度與穩定性相同，但實際上寫入次數較少、速度較快，因此 Timsort 這類混合演算法內部用的是插入排序，而不是泡沫排序。

變體與常見錯誤

• 雞尾酒排序（cocktail shaker sort）在交替的回合中先由左到右、再由右到左，能讓留在尾端的小元素（稱為烏龜）更快移到前面。複雜度仍是 O(n²)。
• 梳排序（comb sort）比較相隔一段間隙的元素並逐步縮小間隙，能提早消除許多烏龜；間隙為 1 時就成了泡沫排序。
• 奇偶排序（odd-even transposition sort）先比較所有奇數對，再比較所有偶數對，常用來教授平行排序。

何時使用泡沫排序

在正式環境的程式碼中幾乎不會用。在 Python 中請呼叫 sorted(items) 或 items.sort()，它們使用 Timsort，時間為 O(n log n) 且穩定。不過泡沫排序仍值得了解：它是最容易解釋的排序法，正確性證明也容易理解，而且是考試或面試中關於迴圈、交換與複雜度的常見入門題。

唯一的實際優勢，是能在單次 O(n) 的走訪中偵測串列是否已排序，但只比較相鄰元素的單純迴圈就能做到，根本不必排序。