簡單講講：我估計能打開我這篇文章的朋友都應該知道冒泡排序吧。我就不那麼系統官方的定義了。我喜歡用執行個體說明，比如給你一個清單L，如下：
[2, 4, 3, 9, 7, 5, 1, 8, 6]
首先我們将2和4比較，4比較大，就保持不變；4和3比較，4比較大，4和3交換位置如下：
[2, 3, 4, 9, 7, 5, 1, 8, 6]
然後4和9比較，保持不變；9和7比較，9大，9和7交換位置，如下：
[2, 3, 4, 7, 9, 5, 1, 8, 6]
然後9和5比較，9大，9和5交換位置，如下：
[2, 3, 4, 7, 5, 9, 1, 8, 6]
9和1比較，9大，9和1交換位置，如下：
[2, 3, 4, 7, 5, 1, 9, 8, 6]
9和8比較，9大，9和8交換位置，如下：
[2, 3, 4, 7, 5, 1, 8, 9, 6]
9和6比較，9大，9和6交換位置，如下：
[2, 3, 4, 7, 5, 1, 8, 6, 9]
至此，經過第1輪“冒泡”之後，清單中最大的數字“9”到了它該到的位置。
以此類推，那麼要經過多少輪才能把這個清單中的元素全都排完呢？
如果你不知道，我們可以用一個長度為3的清單來看看：
[3, 2, 1]
① 3 > 2 => [2, 3, 1]; 3 > 1 => [2, 1, 3]; 3到此排完了
② 1 < 2 => [1, 2, 3]；2到此排完了，剩下一個1，沒有元素和它比較了，于是排序結束。
觀察上面這個例子，3個元素清單，隻需要經過2輪就能排完了，因為剩最後2個元素的時候，它們互相比較一下，這2個元素的順序就都好了，是以當一個清單的長度為len(L)時，隻需要經過len(L)-1輪，排序就結束了，于是冒泡法的第一行代碼就出來了：
for i in range(len(L)-1): #隻需要經過len(L)-1輪，排序即結束，i代表每一輪比較
下面再看看在每輪比較中，一共比較了多少次呢？拿剛開始的清單舉例，
[2, 4, 3, 9, 7, 5, 1, 8, 6] ，經過第1輪後，這個清單變為了
[2, 3, 4, 7, 5, 1, 8, 6, 9]，下一輪再比較，比到6就好了，不需要再和9比較了，對吧！是以我們發現這個規律：
第1輪，比較了len(L) - 1 = 8次；
第2輪，比較了len(L) - 2 = 7次；
第N輪，比較了len(L) - N次，于是代碼又來一行：
for j in range(1, len(L)-i): #這裡面的i就是目前所在的輪數，j表示每一輪要周遊的元素
#這裡面range(1, len(L)-i)也可以寫成range(0,len(L)-i-1),反正表示的長度是一樣的，差別在于
#j的第一個值是0還是1。是0時，先得到第一個元素；是1時，先得到第二個元素。
得到周遊的元素之後，我們就要比較了，相鄰的兩個元素，如果前面的大于後面的，就讓它們的值交換，讓大的往後走，一直到這個清單中最大的元素走到清單的最後面，于是：
if L[j-1] > L[j]: # 假設當j=1時，這裡是第一個元素和第二個元素比較
L[j-1], L[j] = L[j], L[j-1] # Python常用的交換變量寫法
好了，我們的冒泡排序就寫完了。覺得很短嗎？沒錯，實際邏輯代碼就4行。
标配代碼：
L = [2, 4, 3, 9, 7, 5, 1, 8, 6]
for i in range(len(L)-1): #隻需要經過len(L)-1輪，排序即結束，i代表每一輪比較
for j in range(1, len(L)-i):#這裡面的i就是目前所在的輪數，j表示每一輪要周遊的元素
if L[j-1] > L[j]: # 假設當j=1時，這裡是第一個元素和第二個比較
L[j-1], L[j] = L[j], L[j-1] # Python常用的交換變量寫法
print(L)
還可以寫成如下形式，但後續的代碼都以上面的為主：
L = [2, 4, 3, 9, 7, 5, 1, 8, 6]
for i in range(len(L)-1):
for j in range(0, len(L)-i-1): #和上面一樣的，隻是起始索引變了
if L[j] > L[j+1]: #當j=0時，這裡是第一個元素和第二個比較
L[j], L[j+1] = L[j+1], L[j]
print(L)
以上就是冒泡排序的最基礎的代碼。
完了？還有沒有可優化的地方？面前的面試官皺着眉頭對你說。你必須回答：有！
想象有這麼幾種特殊情況情況：
第一種：當周遊一輪發現沒有元素交換時，排序即可結束。
[2, 1, 4, 3, 6, 5, 8, 7, 9] 當待排序清單為這個時，經過第1輪排序，就變成了
[1, 2, 3, 4, 5, 6, 7, 8, 9] 此時清單已經完全排好序了，但是呢，程式不知道，還在準備進入第2輪排序，前後比較，1和2比，2和3比，一直到7和8比完，一個也沒交換，然後緊接着又要進入第3輪了！！停，在這塊是不是可以優化下，我們發現在第2輪比較一遍後，沒有任何值發生交換，那是不是可以說明這輪比較的所有元素全都是有序的了，是以才不需要交換。那我們在程式中可以添加個代表是否交換的變量，不交換時值為False，如果交換了就置為True。最後每輪結束，如果值為False就說明這輪沒有發生交換，沒有發生任何交換就直接結束循環，退出程式，因為這個清單已經排序好了；如果值為True就說明這輪發生交換了，需要進入下一輪，但在進入下一輪周遊前，需要先将已經置為True的變量重新設定為False。如果你想明白了，請看代碼：
L = [2, 4, 3, 9, 7, 5, 1, 8, 6]
for i in range(len(L)-1):
swap = False #每一輪都要重置一次swap的值，是以要寫在這邊
for j in range(1, len(L)-i):
if L[j-1] > L[j]:
swap = True #每次交換就改變swap的值
L[j-1], L[j] = L[j], L[j-1]
if not swap: #當swap為False時，退出循環
break
print(L)
第二種：當清單尾部部分元素提前完成順序時，不再進行比較。
[4, 2, 3, 5, 1, 6, 7, 8, 9] 當待排序清單為這個時，在第1輪排序中，當5和1交換位置後，
[2, 3, 4, 1, 5, 6, 7, 8, 9] 後面的數已經是有序的了，不再需要交換了，最大的數9歸位，第二大的數8也已經歸位，但程式進入第二輪後，繼續逐個比較并確定8在倒數第二個位置上。其實，在第二輪中隻需要比到5的位置就不需要再比較了（或者有個直接的辦法就是直接跳過第二三四五輪）。我們可以記錄每次交換時最後的那個索引，因為自這個索引之後就沒有發生交換了，下次比較的時候隻到這個索引，再往後就不比較了。具體代碼如下：
L = [2, 4, 3, 9, 7, 5, 1, 8, 6]
maxindex = len(L) #索引的初始值應為原先下面len(L)-i的第一個值，即len(L)
for i in range(len(L)-1):
for j in range(1, maxindex): #将之前的len(L)-i替換為上次最後指派的索引ordindex
if L[j-1] > L[j]:
L[j-1], L[j] = L[j], L[j-1]
maxindex = j #記錄索引，多次循環過後，ordindex存儲的是最後被指派的索引
print(L)
第三種：雞尾酒排序，雙向比較交換，無交換時排序結束。
[2, 3, 4, 5, 6, 7, 8, 9, 1] 當待排序清單為這個時，在第1輪排序中，9和1交換位置後，
[2, 3, 4, 5, 6, 7, 8, 1, 9] 發現前面全都排好了，就差個最小值1，如果是按照冒泡算法，第2輪又要經過N-2次比較，最後1和8交換位置，然後又進入第3輪……這時我們發現現在已經在做無用功了，要是經過第1輪之後，第2輪，直接把1這個數一直向前移，一直移到最前面，那樣的話，經過兩輪順序就排好了，這時候配合第一種優化，排好之後直接結束排序就好了，那樣會省很多比較。我們觀察這個清單的特點，普通冒泡法之是以要經過這麼多步驟主要是因為一個清單中最小的數字太靠後了，它沒有辦法盡快滿足第一種優化方案而盡早退出，是以你也可以了解成這個第三種優化是為了更好的實作第一種優化。基于這種特别情況，我們可以采取雙向排序的方式，我每次排一個最大值，然後再排一個最小值，讓小的值盡量提前往前走，這樣有可能提前結束排序。那麼這種優化算法有一種專有的名稱叫“雞尾酒排序”。注意，這種優化主要是針對小的值比較靠後的清單。具體代碼實作如下：
L = [2, 4, 3, 9, 7, 5, 1, 8, 6]
for i in range(len(L)//2):
swap = False
for j in range(i+1, len(L)-i): #起始和結尾都在發生變化
if L[j-1] > L[j]:
L[j-1], L[j] = L[j], L[j-1]
for k in range(len(L)-i-2,i,-1): #倒序來進行小值往前走的操作
if L[k-1] > L[k]:
L[k-1], L[k] = L[k], L[k-1]
swap = True #隻需将交換變量放在最後面的循環即可
if not swap:
break
print(L)
#以上代碼是 第一種優化+雙向交換 = 雞尾酒排序
目前能想到的優化就這麼多了，最後把 第二種和第三種(已包括第一種)再融合一下，湊成
最終優化版本：
L = [2, 4, 3, 9, 7, 5, 1, 8, 6]
minindex = 0
maxindex = len(L)
for i in range(len(L)//2):
swap = False
for j in range(minindex+1, maxindex):
if L[j-1] > L[j]:
L[j-1], L[j] = L[j], L[j-1]
maxindex = j
for k in range(maxindex-1, minindex, -1):
if L[k-1] > L[k]:
L[k-1], L[k] = L[k], L[k-1]
minindex = k #目前半段提前完成排序時也不用再比較了
swap = True
if not swap:
break
print(L)
附加說明：上面那三種優化及最終優化版都隻是針對特殊情況的，那如果沒有特殊情況，其實效率和普通冒泡法基本上是一樣的，後面我會做個測試，看看優化後的版本性能到底性能會好多少。冒泡排序的時間複雜度為O(n²)，空間複雜度為O(1)，這些是不變的，即使優化後也是如此。但是可以再細算一點，就拿最标配代碼看，
3個元素的清單，要比較2+1=3次；
4個元素的清單，要比較3+2+1=6次；
5個元素的清單，要比較4+3+2+1=10次；
N個元素的清單，要比較N(N-1)/2次（找規律應該會吧）。
是以這個時間複雜度O(n²)是從
這裡來的，算複雜度的時候把系數及低項數去掉了，但是如果兩個算法時間複雜度都是O(n²)，那麼他們的系數的不同就會影響到他們的計算時間了。比如有10個元素的清單，一個比較了100(n²)次，一個比較了50(1/2n²)次，他們的速度還是有差别的。然後再說一下穩定性，一般來說冒泡排序是穩定的，因為相同的元素是直接跳過的，具體對應的代碼為【if L[j-1]> L[j]:】，這裡是前面比後面大才交換，前面和後面相等或者小于是不交換的，這就保證了冒泡排序的穩定性，但是如果我把這行代碼改成 【if L[j-1] >= L[j]:】那它就不穩定了，因為相等的時候，你也把它交換了，這時你也可以說它是不穩定的。但是完全沒必要這麼做，因為這做了無用功，相等你還交換啥。是以一般情況下，冒泡排序是穩定的排序。
優化測試：我們對上面的标配版冒泡排序和優化版冒泡排序做個測試比較，分别選取元素個數為20、200、2000的随機清單。
import timeit #一個時間測試子產品，用來計算一段代碼執行num次的執行時間
import random
def nom_sort(L): #标配版函數
for i in range(len(L)-1):
for j in range(1, len(L)-i):
if L[j-1] > L[j]:
L[j-1], L[j] = L[j], L[j-1]
return L
def opt_sort(L): #優化版函數
minindex = 0
maxindex = len(L)
for i in range(len(L)//2):
swap = False
for j in range(minindex+1, maxindex):
if L[j-1] > L[j]:
L[j-1], L[j] = L[j], L[j-1]
maxindex = j
for k in range(maxindex-1, minindex, -1):
if L[k-1] > L[k]:
L[k-1], L[k] = L[k], L[k-1]
minindex = k
swap = True
if not swap:
break
return L
res = []
number = 200 # 20, 200, 2000
M = list(range(0,number))
for i in range(1000): #循環次數 10000 1000 100
random.shuffle(M) #随機打散
N = M[:]
res.append([timeit.timeit('nom_sort(M)', number=1, globals=globals()),
timeit.timeit('opt_sort(N)', number=1, globals=globals())] )
#分别執行兩個函數，計算執行number次的總時間，為保證穩定性和公平性用for循環測試多次
print('%.8f%.8f' % tuple([sum([i[j] for i in res])/len(res) for j in range(2)]))
#計算兩個函數的各自平均秒數
### output ###
元素數 循環次數 标配版 優化版 提高效率
20 10000 0.00005097 0.00004247 16.7 %
200 1000 0.00404639 0.00338712 16.3 %
2000 100 0.46240990 0.40061400 13.4 %
總結：根據上面測試分析，優化後的代碼大概效率會提升15%左右，而且随着元素數的增加，效率應該會逐漸減小。好了，咱們的冒泡排序差不多就講完了。下一篇：選擇排序。