目錄
1.冒泡排序
原理
代碼（python&cpp）
拓展：timeit()用法
2.選擇排序
原理
3.插入排序
原理
代碼（python&cpp）
4.歸并排序
原理
代碼
5.快速排序
原理
代碼（python&cpp）
6.計數排序
原理
代碼（python&cpp）
總結
參考
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版）--胡松濤
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/379480.html
標籤：其他