為什麼突然研究氣泡排序？
每學期我都會教高一學生氣泡排序。然而有一天我和朋友聊天，發現有很多不同版本的氣泡排序，於是我深入研究，探索氣泡排序的歷史。
另外，原本用英文寫，但發現這個平台應該大部分是讀中文，於是又翻譯了自己的文章改為中文版。
我們所知道的氣泡排序
氣泡排序是一種非常常見且易於學習的演算法。假設你要對一組數字進行排序，並希望按從小到大的順序排列。然後，你從左邊開始比較相鄰的數字，如果順序不正確（在這種情況下，左邊的數字大於右邊的數字），就交換它們。我們稱之為一個階段。我們最多可以重複這個過程 n-1 次；然後，數組將被排序。
我們可以將虛擬碼寫作如下：
重複 n-1 次：
對於索引 i 從第一個到最後第二個：
如果 array[i] > array[i + 1]:
交換這兩個數字的位置。
大家可能聽過許多其他版本，特別是上面的稍微改進版本。也就是在第 k 階段，我們從第一個數字比較到第 n-k 個數字。
所以虛擬碼修訂為：
重複 n-1 次：
對於索引 i 從第一個到第 n-k 個索引：
如果 array[i] > array[i + 1]:
交換這兩個數字的位置。
氣泡排序的歷史
我朋友有次告訴我，最原始的版本是“從後面開始比較”而不是我們通常學習的“從前面開始比較”。
因此，我去查找氣泡排序的歷史及其原始論文。這裡有兩篇關鍵論文：
1. Sorting on Electronic Computer Systems，Edward Harry Friend，1955年。
2. A Programming Language，Kenneth E. Iverson，1962年。
Friend [1] 使用“交換”來描述氣泡排序。此外，他指出排序從開始開始，也就是“從前面開始”。
At the beginning of each pass the first abbreviated item is compared with the second and the smaller assumes first position.
另一方面，Iverson [2] 首先提出了“氣泡排序”這個詞，並指出比較從數字的底部開始，較小的數字向上移動，也就是“從後面開始”。
The basic operation of the bubble sort is the comparison and possible transposition of a pair of adjacent items so as to place the smaller of the two keys earlier in the sequence. The first stage consists of such operations performed in sequence on the item pairs (xᵥ₋₁, xᵥ), (xᵥ₋₂, xᵥ₋₁), ⋯, (x₁, x₂) .
Iverson, 1962
一些事實：
- 考慮效率，向上和向後之間沒有差別。
- 原始的“氣泡排序” [2] 是從後面開始比較而不是我們通常知道的從前面開始比較。
- 兩篇論文都有設定終止條件，即在過程中如果向量已經排序，則終止過程。這通常在教科書中介紹氣泡排序時不會提到。
如何正確介紹氣泡排序
那麼，根據這兩篇論文，如何正確介紹氣泡排序呢？以下是我的觀點及建議。
首先，解釋氣泡排序的核心概念，即通過比較相鄰的數字來排序向量，如果順序不是我們想要的，則進行交換。這一概念源自 Friend [1] 的交換（Exchanging）。
其次，說明 Iverson [2] 的歷史，他首次提出“氣泡排序”這個詞。想像一下海底有許多氣泡，從底部開始，較輕的上升，較重的下沉。這意味著我們從最後一個數字開始比較，最終向量變為由小到大。此時，如果你不打算寫程式或解釋如何實作，我認為 Iverson 的版本更容易理解為什麼叫做“氣泡排序”。
第三，如果你想繼續實作，可以選擇從後比較，或從前比較。在這裡，我經常以從前比較的方式教我的學生。
教學指導
以下是我逐步教學生氣泡排序概念的示例。
第一個是效率的折衷版本，非常容易理解，但同時浪費時間。（但 CPU 運行得非常快，所以這不重要。）
nums = [1, 2, 9, 8, 3]
n = len(nums)
t = 0
for k in range(n - 1):
for i in range(n - 1):
t += 1
if (nums[i] > nums[i + 1]):
nums[i], nums[i + 1] = nums[i + 1], nums[i]
print(f'{nums = }, 比較 {t} 次.')
# nums = [1, 2, 3, 8, 9], 比較 16 次.
接下來我會說，正如我們在第 k 階段所見，最大的 k-1 個數字是固定的，所以我們不需要比較它們。
nums = [1, 2, 9, 8, 3]
n = len(nums)
t = 0
for k in range(n - 1):
for i in range(n - k - 1):
t += 1
if (nums[i] > nums[i + 1]):
nums[i], nums[i + 1] = nums[i + 1], nums[i]
print(f'{nums = }, 比較 {t} 次.')
# nums = [1, 2, 3, 8, 9], 比較 10 次.
最後，在某些情況下，向量已經排序，在一個階段內沒有交換，然後我們可以終止它，這樣可以進一步優化。
nums = [1, 2, 9, 8, 3]
n = len(nums)
t = 0
for k in range(n - 1):
hasSwapped = False
for i in range(n - k - 1):
t += 1
if (nums[i] > nums[i + 1]):
hasSwapped = True
nums[i], nums[i + 1] = nums[i + 1], nums[i]
if not hasSwapped:
break
print(f'{nums = }, 比較 {t} 次.')
# nums = [1, 2, 7, 8, 9], 比較 9 次.
讀者可以隨意使用這些作為教學材料。但如需商業用途，請聯繫我。
