在生活中，我們離不開排序，比如我們上學的時候按個頭高低排位置，現在我們買東西的時候會按照發貨地遠近進行排序，或者價格高低排序。
排序看著簡單，可是背後藏著很多的算法和思想。在這給大家介紹一下常用的排序算法。
每次提到排序，繞不開的就是冒泡排序。
冒泡排序（Bubble sort）是一種基礎的交換排序。它的基本思想是：兩兩比較相鄰記錄的關鍵字，如果反序則交換，直到沒有反序的記錄為止。這個算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頂端（升序或降序排列），就如同碳酸飲料中二氧化碳的氣泡最終會上浮到頂端一樣，故名“冒泡排序”。
我們先來看一個例子。
有這麼8個數字組成的無序數列[5,8,6,3,9,2,1,7]，希望按照從小到大的順序對其進行排序。
按照冒泡排序的算法，我們需要鏈路比較相鄰紀錄的關鍵字，如果一個元素大於右邊相鄰元素時，交換他們的位置，當一個元素小於或等於右邊元素，位置不變。
第一趟下來，元素9作為這個數列中最大的元素，就像是汽水裡的氣泡一樣，冒到了最右側。
再來第二趟：
第二次交換結束，8作為未排序中的最大元素被冒到右側第二位置上。
將未排序的都遍歷過之後，所有的元素都會變為有序，這就是冒泡排序的思路。
接下來，我們來實現這個代碼，代碼非常簡單，使用雙循環實現。內部循環控制每一輪的最大元素冒泡處理，外部循環控制所有元素的依次排序。
def bubble_sort(nums):
for i in range(len(nums) - 1): # 這個循環負責設置冒泡排序進行的次數
for j in range(len(nums) - i - 1): # 內部循環控制每一輪的最大元素冒泡處理
if nums[j] > nums[j + 1]:
nums[j], nums[j + 1] = nums[j + 1], nums[j]
return nums
print(bubble_sort([5,8,6,3,9,2,1,7]))
# 輸出：[1, 2, 3, 5, 6, 7, 8, 9]
我們來看看冒泡排序的基本性能：
關於穩定性：因為在比較的過程中，當兩個相同大小的元素相鄰，只比較大或者小，所以相等的時候是不會交換位置的。而當兩個相等元素離著比較遠的時候，也只是會把他們交換到相鄰的位置。他們的位置前後關係不會發生任何變化，所以算法是穩定的。
冒泡排序是一種比較好理解的排序，但是整體的性能相比較來說比較差，因此需要進行優化。
我們來看一個特殊情況。
如果按照上面說的算法去進行計算，我們加一點代碼進去看看具體排序情況：
def bubble_sort(nums):
for i in range(len(nums) - 1): # 這個循環負責設置冒泡排序進行的次數
for j in range(len(nums) - i - 1): # 內部循環控制每一輪的最大元素冒泡處理
if nums[j] > nums[j + 1]:
nums[j], nums[j + 1] = nums[j + 1], nums[j]
print("第", i , "次排序後:", end='')
for n in nums:
print(n, end=' ,')
print(" ")
return nums
print(bubble_sort([1,3,4,5,6,7,8,9]))
實際輸出：
第 0 次排序後:1 ,3 ,4 ,5 ,6 ,7 ,8 ,9 ,
第 1 次排序後:1 ,3 ,4 ,5 ,6 ,7 ,8 ,9 ,
第 2 次排序後:1 ,3 ,4 ,5 ,6 ,7 ,8 ,9 ,
第 3 次排序後:1 ,3 ,4 ,5 ,6 ,7 ,8 ,9 ,
第 4 次排序後:1 ,3 ,4 ,5 ,6 ,7 ,8 ,9 ,
第 5 次排序後:1 ,3 ,4 ,5 ,6 ,7 ,8 ,9 ,
第 6 次排序後:1 ,3 ,4 ,5 ,6 ,7 ,8 ,9 ,
[1, 3, 4, 5, 6, 7, 8, 9]
我們能看到在第一次循環的時候，整個數列已經是有序的，但是常規版的算法依然會繼續流程，浪費很多的時間，而這些都是多餘的。
如果我們能判斷出數列已經有序，並且做出標記，那麼剩下的幾輪排序就不必執行了，可以提前結束工作。我們來改良一下代碼：
def bubble_sort(nums):
for i in range(len(nums) - 1): # 這個循環負責設置冒泡排序進行的次數
#有序標記，每一輪的初始值都是True
is_sorted = True
for j in range(len(nums) - i - 1): # 內部循環控制每一輪的最大元素冒泡處理
if nums[j] > nums[j + 1]:
#因為有元素進行交換，所以不是有序的，標記變為False
nums[j], nums[j + 1] = nums[j + 1], nums[j]
is_sorted = False
print("第", i , "次排序後:", end='')
for n in nums:
print(n, end=' ,')
print(" ")
if is_sorted:
break
return nums
print(bubble_sort([1,3,4,5,6,7,8,9]))
# 輸出：[1, 3, 4, 5, 6, 7, 8, 9]
加上這個標記位之後，我們再來運行一下：
第 0 次排序後:1 ,3 ,4 ,5 ,6 ,7 ,8 ,9 ,
[1, 3, 4, 5, 6, 7, 8, 9]
可以看到，當整體數列已經有序的基礎上，不需要再進行後續的多次排序時間浪費了。整體的最好時間就優化為O(n)。
最後祝大家學習愉快。
作 者：Testfan Chris
出 處：微信公眾號：自動化軟件測試平臺
閱讀更多 安然—Testfan 的文章
