[leetcode]排序演演算法（氣泡排序，選擇排序，插入排序，快速排序，計數排序）
目錄
1.氣泡排序
氣泡排序（Bubble Sort）是一種很原始的排序方法，就是通過不斷地交換「大數」的位置達到排序的目的。因為不斷出現「大數」類似於水泡不斷出現，因此被形象地稱為冒泡演演算法。
原理
冒泡演演算法的基本原理就是比較相鄰兩個數位的大小。將兩數中比較大的那個數交換到靠後的位置。不斷地交換下去就可以將最大的那個數放到佇列的尾部。然後重頭再次交換，直到將數列排成有序數列。
一個 n 個數的數列需要排序 n -1輪。這樣可以確保得到一個有序的數列。因此氣泡排序的時間複雜度是 
。
程式碼（python&cpp）
#!/user/bin/env/python3
#-*-conding:utf-8 -*-
# data:20211210
# author:yang
import random
import timeit
def randomList(n):
"""返回一個長度為n的整數列表，資料範圍為[0,1000)"""
iList = []
for i in range(n):
iList.append(random.randrange(1000))
return iList
def bubbleSort(iList):
"""氣泡排序"""
if len(iList) <= 1:
return iList
for i in range(1,len(iList)):
for j in range(0,len(iList)-i):
if iList[j] >= iList[j+1]:
iList[j],iList[j+1] = iList[j+1],iList[j]
print("第%d輪排序結果"%i,end=" ")
print(iList)
# return iList
if __name__=="__main__":
iList = randomList(10)
print("iList:",iList)
print(bubbleSort(iList))
# bubbleSort(iList)
# print(timeit.timeit("bubbleSort(iList)","from __main__ import bubbleSort,iList", number=100))
cpp待補充
拓展：timeit()用法
python中的timeit（）方法， 它用於獲取程式碼的執行時間。該庫將程式碼語句預設執行一百萬次，並提供從集合中花費的最短時間，可以用來檢查程式碼的效能。
語法：
timeit.timeit(stmt, setup,timer, number)引數：
stmt：這將採用您要測量其執行時間的程式碼。預設值為「pass」。
setup：這將包含需要在stmt之前執行的設定詳細資訊。這個引數可以將stmt的環境傳進去。比如各種import和引數什麼的。預設值為「 pass」。
timer：它將具有計時器值，timeit（）已經設定了預設值，我們可以忽略它。
number：stmt將按照此處給出的編號執行。預設值為1000000。
注：
要使用timeit（），我們需要匯入模組，如下：
import timeit
另外需要補充一點是，如果你想直接 stmt 那裡執行函數。可以把函數申明在當前檔案中，然後在 stmt = ‘func()’ 執行函數。然後使用 setup = ‘from __main__ import func’ 即可，如果要import 多個需要使用 setup = from __main__ import func; import simplejson'
2.選擇排序
原理
簡單地說，選擇排序只做了一件事，就是從數列中選擇最大（最小）的那個數，將這個數放到合適的位置。然後在拋開這個數的子數列中找最大（最小）的那個數放到合適的位置。然後……一直到子數列為空為止。與氣泡排序稍有不同的是，它不是相鄰的兩個數比較，而是某個數和數列中其他所有的數比較。
第一輪排序：以數列中第1個數為基數，遍歷數列中其他的數位，找到最小的那個數，然後交換這兩個數的位置。 本輪排序的結果將數列中最小的那個數放到了數列的第一位。
第二輪排序：然後以數列中的第2個數為基數，遍歷數列中剩餘的其他數位，找到最小的那個數，交換這兩個數的位置。第二個數位3已經是剩餘數列中最小的數了。因此本輪無須交換數位，
第N輪排序：按照這個規律，不斷地找剩餘數列中最小的數位，交換位置，直到將原始數列排成有序數列。
選擇排序數列完畢。共6個數，排序了5輪。理論上來說，選擇排序的時間複雜度是 O ( n 2 )。但在Python中稍微有點特殊，因為Python 列 表 中 尋 找 最 小 的 那 個 數 不 需 要 逐 個 比 較 ， 使 用min(iList[i:])就可以得到最小的那個數，所以使用Pythonic風格版本的選擇排序，時間複雜度是 O ( n )。因此，理論上在Python版本的排序演演算法中選擇排序演演算法是最快的。
程式碼（python&cpp）
#!/user/bin/env/python3
#-*-conding:utf-8 -*-
# data:20211210
# author:yang
from randomList import randomList
import timeit
def selectionSort(iList):
if len(iList) <= 1:
return iList
for i in range(0,len(iList)-1):
if iList[i] != min(iList[i:]):
minIndex = iList.index(min(iList[i:])) # 最小數的下標
iList[i],iList[minIndex] = iList[minIndex],iList[i]
print("第%d輪排序結果："%(i+1),end=" ")
print("ilist:",iList)
# return iList
if __name__ == "__main__":
iList = randomList(10)
print(iList)
print(selectionSort(iList))
# print(timeit.timeit("selectionSort(iList)","from __main__ import selectionSort,iList",number = 1)) cpp待補充
3.插入排序
插入排序（Insertion Sort）可能是最容易理解的排序了，插入排序方法與打撲克取牌的排序很相似。在打撲克時，每取一張新牌，都會與手上已有的牌進行比較，將新牌插入到比自己小的牌後面。在取完所有的牌後，手上已有的牌就是個有序的序列。
原理
插入排序首先將數列分成兩部分。數列的第一個數為left部分，其他的數為right部分。然後將right部分中的數逐一取出，插入left部分中合適的位置。當right部分為空時，left部分就成為了一個有序
數列。
舉例：
第一輪：
首先要做的是將數列分成左、右兩部分，left部分是第一個數位，right部分是數列剩餘的部分。首先在牌堆中取出第一張牌，牌面是7，
第二輪排序
然後從牌堆中取出第二張牌，牌面是3。將牌面是3的牌放入手中合適的位置。將right部分的第一個數位3插入left部分合適的位置。3比7要小，插入到7的前面。
第N輪排序
迴圈將right部分的數位插入left部分，插入排序的時間複雜度是 O ( n 2 )。
程式碼（python&cpp）
#!/user/bin/env/python3
#-*-conding:utf-8 -*-
# data:20211210
# author:yang
from randomList import randomList
import timeit
def insertSort(iList):
if len(iList) <= 1:
return iList
for right in range(1,len(iList)):
target = iList[right]
for left in range(0,right):
if target <= iList[left]:
# 使用python切片賦值
iList[left+1:right+1] = iList[left:right]
iList[left] = target
break
return iList
if __name__ == "__main__":
iList = randomList(10)
print(iList)
print(insertSort(iList))
# print(timeit.timeit("selectionSort(iList)","from __main__ import selectionSort,iList",number = 1))
cpp待補充
4.歸併排序
歸併排序（Merge Sort）是一種典型的遞迴法排序。它把複雜的排序過程分解成一個簡單的合併子序列的過程。至於怎麼得到這個子序列，就得自己呼叫自己了。
原理
歸併排序首先要做的就是將數列分成左右兩部分（最好是等分），然後將左、右兩個子數列排序完畢後再合併到一起就成了一個有序數列。左、右兩個子數列怎麼變成有序數列呢？那就回頭呼叫自
己，再把子數列分成左、右兩部分，直到將所有的子數列的長度分為1為止。然後把子子數列排序完畢後合併成子數列……有點像那個著名的故事，山上有座山，山裡有座廟，廟裡有兩個和尚……。和尚講故事是無窮無盡的，幸運的是數列的長度即使再大也不會是無盡的。所以當子子子……序列分到不可再分割的時候（最小的序列長度為1時），就可以返回開始合併數列了。逐步合併子子子子……數列，到最後就得到了一個新的有序數列。
第一次分組
第二次分組
經過三次分組，已經將所有的子子子數列都變成了長度為1的數列。現在可以確定這些長度為1的數列必定是有序數列了，然後開始反向合併這些數列。
第一次合併
這裡還需要考慮left和right長度不一致的情況。先合併數列[3]、[5]以及[9]、[4]。
第二次合併
第三次合併
歸併排序完畢。經過3次合併，最終得到了一個有序數列。歸併排序的時間複雜度是 O ( n Log n） )。
程式碼
#!/user/bin/env/python3
#-*-conding:utf-8 -*-
# data:20211210
# author:yang
from randomList import randomList
import timeit
def mergeSort(iList):
if len(iList) <= 1:
return iList
middle = len(iList)//2
left,right = iList[0:middle],iList[middle:]
return mergeList(mergeSort(left),mergeSort(right))
def mergeList(left,right):
"""合併序列"""
mList = []
while left and right:
if left[0] >= right[0]:
mList.append(right.pop(0))
else:
mList.append(left.pop(0))
while left:
mList.append(left.pop(0))
while right:
mList.append(right.pop(0))
return mList
if __name__ == "__main__":
iList = randomList(10)
print(iList)
print(mergeSort(iList))
# print(timeit.timeit("selectionSort(iList)","from __main__ import selectionSort,iList",number = 1))
5.快速排序
快速排序（Quick Sort）演演算法也是一種遞迴排序，用簡單的方法來解決複雜的問題，唯一不太好的地方就是稍微有點浪費空間。
原理
以列表中的任意一個數為基準（一般選擇列表中的第一個數），將列表分為左、右（前、後）兩個子列表：左邊子列表的數要比基準數小，右邊子列表的數要比基準數大。然後繼續把左邊子列表和右邊子列表按同樣的方法繼續分解、比較，一直到分無可分為止。然後按照左邊子列表（比基準數小）+基準數+右邊子列表（比基準數大）的方式連線起來。最後得到一個有序的數列。
以數列[7,3,5,1,9,4]為例。
第一次分組
以「7」為基準，比7小的分在左邊的子數列中，比7大的分在右邊的子數列中。
此時左邊的子序列有4個數[3, 5, 1, 4]，還需要繼續分組。右邊的子序列中只有一個數9，不需要再分了。第二次只需要將左邊的部分分組排序就可以了。
第二次分組
左邊的子序列還剩下[3, 5, 1, 4]，現在以第一個數3為基準數，將後面部分的[5, 1, 4]分成兩部分。同樣還是比基準數（3）小的放到左邊子序列，比基準數（3）大的放到右邊子序列。
數分組完畢後。只要按照一定的順序重新組合起來就可以了。組合很簡單，就是小的數（左邊部分）+中間數（基準數）+大的數（右邊部分）。
第一次合併
將子序列合併，具體規則是left + [base] + right。這裡需要稍微注意一下，left和right都是序列（列表），而base部分是單獨的一個數，所以需要將它序列化。
第二次合併
第三次合併
經過3次分組、合併後，得到了有序數列。快速排序的時間複雜度最壞的情況下是 O ( n 2 )。
程式碼（python&cpp）
#!/user/bin/env/python3
#-*-conding:utf-8 -*-
# data:20211210
# author:yang
from randomList import randomList
import timeit
def quickSort(iList):
if len(iList) <= 1:
return iList
left = []
right = []
for i in iList[1:]:
if i <= iList[0]:
left.append(i)
else:
right.append(i)
return quickSort(left) + [iList[0]] + quickSort(right)
if __name__ == "__main__":
iList = randomList(10)
print(iList)
print(quickSort(iList))
# print(timeit.timeit("selectionSort(iList)","from __main__ import selectionSort,iList",number = 1))注：此方法速度快。
6.計數排序
計數排序（Counting Sort）演演算法是一種比較特殊的演演算法，因為它不是一個基於比較的演演算法。將兩個數進行比較，將大的數放後面、小的數放前面，這樣的演演算法都是基於比較的演演算法。
原理
它採用了一個巧妙的方法，選擇一個數為基數，然後統計整個數列中有多少個數比基數小。如果有 n 個數比基數小，那麼基數就放到新數列的第n +1的位置上（rList[n]）。以數列[7, 3, 5, 1, 9, 4]為例，首先要做的是先建立一個與[7, 3, 5, 1, 9, 4]相同長度的空數列。
第一個數的位置
第二個數的位置
第三個數的位置
依次類推
將所有的數位都插入到新數列後，排序就完成了。計數排序的時間複雜度是 O ( n + k )，其中 k 是整數的範圍。
程式碼（python&cpp）
#!/user/bin/env/python3
#-*-conding:utf-8 -*-
# data:20211210
# author:yang
from randomList import randomList
import timeit
def countingSort(iList):
if len(iList) <= 1:
return iList
iLen = len(iList)
rList = [None]*iLen
for i in range(iLen):
small = 0 # 比基數小的
same = 0 # 與基數相等的
for j in range(iLen):
if iList[j] < iList[i]:
small += 1
elif iList[j] == iList[i]: # 相同的數
same += 1
for k in range(small,small+same):
rList[k] = iList[i]
return rList
if __name__ == "__main__":
iList = randomList(10)
print(iList)
print(countingSort(iList))
# print(timeit.timeit("selectionSort(iList)","from __main__ import selectionSort,iList",number = 1))
總結
從表格上來看，排序100次用時最少，速度最快的應該是快速排序。果然是名副其實。選擇排序的速度與快速排序相差無幾。用時最多、速度最慢的是插入排序，其次就是氣泡排序。當然，根據輸入數列的不同，這個排名可能會有所變動。
參考
圖解leetcode初級演演算法（python版）--胡松濤