10個python3常用排序算法詳細說明與實例（快速排序，冒泡排序，桶排序，基數(shù)排序，堆排序，希爾排序，歸并排序，計數(shù)排序）
我簡單的繪制了一下排序算法的分類，藍色字體的排序算法是我們用python3實現(xiàn)的，也是比較常用的排序算法。
Python3常用排序算法
1、Python3冒泡排序——交換類排序
冒泡排序（Bubble Sort）也是一種簡單直觀的排序算法。
它重復地走訪過要排序的數(shù)列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。
走訪數(shù)列的工作是重復地進行直到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)排序完成。這個算法的名字由來是因為越小的元素會經(jīng)由交換慢慢"浮"到數(shù)列的頂端。
作為最簡單的排序算法之一，冒泡排序給我的感覺就像Abandon在單詞書里出現(xiàn)的感覺一樣，每次都在第一頁第一位，所以最熟悉。
冒泡排序還有一種優(yōu)化算法，就是立一個 flag，當在一趟序列遍歷中元素沒有發(fā)生交換，則證明該序列已經(jīng)有序。
但這種改進對于提升性能來說并沒有什么太大作用。
最快：當輸入的數(shù)據(jù)已經(jīng)是正序時（都已經(jīng)是正序了，我還要你冒泡排序有何用?。?/p>
最慢：當輸入的數(shù)據(jù)是反序時（寫一個 for 循環(huán)反序輸出數(shù)據(jù)不就行了，干嘛要用你冒泡排序呢，我是閑的嗎）
Python3冒泡排序?qū)嵗a
# 冒泡排序
def bubbleSort(arr):
for i in range(1, len(arr)):
for j in range(0, len(arr)-i):
if arr[j] > arr[j+1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
if __name__ == '__main__':
list = [1, 5, 8, 123, 22, 54, 7, 99, 300, 222]
print("List source is:", list)
result = bubbleSort(list)
print("List sort is:", result)
效果
2、Python3快速排序-交換類排序
快速排序是由東尼·霍爾所發(fā)展的一種排序算法。
在平均狀況下，排序 n 個項目要 Ο(nlogn) 次比較。在最壞狀況下則需要 Ο(n2) 次比較，但這種狀況并不常見。事實上，快速排序通常明顯比其他 Ο(nlogn) 算法更快，因為它的內(nèi)部循環(huán)（inner loop）可以在大部分的架構(gòu)上很有效率地被實現(xiàn)出來。
快速排序使用分治法（Divide and conquer）策略來把一個串行（list）分為兩個子串行（sub-lists）。
快速排序又是一種分而治之思想在排序算法上的典型應(yīng)用。本質(zhì)上來看，快速排序應(yīng)該算是在冒泡排序基礎(chǔ)上的遞歸分治法。
快速排序的名字起的是簡單粗暴，因為一聽到這個名字你就知道它存在的意義，就是快，而且效率高！它是處理大數(shù)據(jù)最快的排序算法之一了。
特點：選基準、分治、遞歸
Python3快速排序-交換類排序?qū)嵗创a
# 快速排序
def quickSort(arr, left=None, right=None):
left = 0 if not isinstance(left,(int, float)) else left
right = len(arr)-1 if not isinstance(right,(int, float)) else right
if left < right:
partitionIndex = partition(arr, left, right)
quickSort(arr, left, partitionIndex-1)
quickSort(arr, partitionIndex+1, right)
return arr
def partition(arr, left, right):
pivot = left
index = pivot+1
i = index
while i <= right:
if arr[i] < arr[pivot]:
swap(arr, i, index)
index+=1
i+=1
swap(arr,pivot,index-1)
return index-1
def swap(arr, i, j):
arr[i], arr[j] = arr[j], arr[i]
if __name__ == '__main__':
list = [1, 5, 8, 123, 22, 54, 7, 99, 300, 222]
print("List source is:", list)
result = quickSort(list)
print("List sort is:", result)
Python3快排簡寫
def quickSort2(array): return array if len(array) <= 1 else quickSort2([lt for lt in array[1:] if lt < array[0]]) + array[0:1] + quickSort2([ge for ge in array[1:] if ge >= array[0]])
效果
3、Python3選擇排序-選擇類排序
選擇排序是一種簡單直觀的排序算法。
無論什么數(shù)據(jù)進去都是 O(n2) 的時間復雜度。所以用到它的時候，數(shù)據(jù)規(guī)模越小越好。唯一的好處可能就是不占用額外的內(nèi)存空間了吧。
Python3選擇排序-選擇類排序?qū)嵗创a
# 選擇排序
def selectionSort(arr):
for i in range(len(arr) - 1):
# 記錄最小數(shù)的索引
minIndex = i
for j in range(i + 1, len(arr)):
if arr[j] < arr[minIndex]:
minIndex = j
# i 不是最小數(shù)時，將 i 和最小數(shù)進行交換
if i != minIndex:
arr[i], arr[minIndex] = arr[minIndex], arr[i]
return arr
if __name__ == '__main__':
list = [1, 5, 8, 123, 22, 54, 7, 99, 300, 222]
print("List source is:", list)
result = selectionSort(list)
print("List sort is:", result)
效果
4、Python3堆排序-選擇類排序
堆排序（Heapsort）是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計的一種排序算法。
堆積是一個近似完全二叉樹的結(jié)構(gòu)，并同時滿足堆積的性質(zhì)：即子結(jié)點的鍵值或索引總是小于（或者大于）它的父節(jié)點。堆排序可以說是一種利用堆的概念來排序的選擇排序。分為兩種方法：
1、大頂堆（大根堆）：每個節(jié)點的值都大于或等于其子節(jié)點的值，在堆排序算法中用于升序排列；
2、小頂堆（小根堆）：每個節(jié)點的值都小于或等于其子節(jié)點的值，在堆排序算法中用于降序排列；
堆排序的平均時間復雜度為 Ο(nlogn)。
Python3堆排序-選擇類排序?qū)嵗创a
# 堆排序
def buildMaxHeap(arr):
import math
for i in range(math.floor(len(arr)/2),-1,-1):
heapify(arr,i)
def heapify(arr, i):
left = 2*i+1
right = 2*i+2
largest = i
if left < arrLen and arr[left] > arr[largest]:
largest = left
if right < arrLen and arr[right] > arr[largest]:
largest = right
if largest != i:
swap(arr, i, largest)
heapify(arr, largest)
def swap(arr, i, j):
arr[i], arr[j] = arr[j], arr[i]
def heapSort(arr):
global arrLen
arrLen = len(arr)
buildMaxHeap(arr)
for i in range(len(arr)-1,0,-1):
swap(arr,0,i)
arrLen -=1
heapify(arr, 0)
return arr
if __name__ == '__main__':
list = [1, 5, 8, 123, 22, 54, 7, 99, 300, 222]
print("List source is:", list)
result = heapSort(list)
print("List sort is:", result)
效果
5、Python3插入排序-插入類排序
插入排序是一種最簡單直觀的排序算法。
插入排序的代碼實現(xiàn)雖然沒有冒泡排序和選擇排序那么簡單粗暴，但它的原理應(yīng)該是最容易理解的了，因為只要打過撲克牌的人都應(yīng)該能夠秒懂。
它的工作原理是通過構(gòu)建有序序列，對于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。
插入排序和冒泡排序一樣，也有一種優(yōu)化算法，叫做拆半插入。
Python3插入排序-插入類排序?qū)嵗创a
# 作者：沙振宇
# 插入排序
def insertionSort(arr):
for i in range(len(arr)):
preIndex = i-1
current = arr[i]
while preIndex >= 0 and arr[preIndex] > current:
arr[preIndex+1] = arr[preIndex]
preIndex-=1
arr[preIndex+1] = current
return arr
if __name__ == '__main__':
list = [1, 5, 8, 123, 22, 54, 7, 99, 300, 222]
print("List source is:", list)
result = insertionSort(list)
print("List sort is:", result)
效果
6、Python3希爾排序-插入類排序
希爾排序，也稱遞減增量排序算法，是插入排序的一種更高效的改進版本。
但希爾排序是非穩(wěn)定排序算法。
希爾排序是基于插入排序的以下兩點性質(zhì)而提出改進方法的：
1、插入排序在對幾乎已經(jīng)排好序的數(shù)據(jù)操作時，效率高，即可以達到線性排序的效率；
2、但插入排序一般來說是低效的，因為插入排序每次只能將數(shù)據(jù)移動一位；
希爾排序的基本思想是：
先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序，待整個序列中的記錄"基本有序"時，再對全體記錄進行依次直接插入排序。
Python3希爾排序-插入類排序?qū)嵗创a
# 作者：沙振宇
# 希爾排序
def shellSort(arr):
import math
gap=1
while(gap < len(arr)/3):
gap = gap*3+1
while gap > 0:
for i in range(gap,len(arr)):
temp = arr[i]
j = i-gap
while j >=0 and arr[j] > temp:
arr[j+gap]=arr[j]
j-=gap
arr[j+gap] = temp
gap = math.floor(gap/3)
return arr
if __name__ == '__main__':
list = [1, 5, 8, 123, 22, 54, 7, 99, 300, 222]
print("List source is:", list)
result = shellSort(list)
print("List sort is:", result)
效果
7、Python3歸并排序-歸并類排序
歸并排序（Merge sort）是建立在歸并操作上的一種有效的排序算法。
該算法是采用分治法（Divide and Conquer）的一個非常典型的應(yīng)用。
作為一種典型的分而治之思想的算法應(yīng)用，歸并排序的實現(xiàn)由兩種方法：
1、自上而下的遞歸（所有遞歸的方法都可以用迭代重寫，所以就有了第 2 種方法）；
2、自下而上的迭代；
和選擇排序一樣，歸并排序的性能不受輸入數(shù)據(jù)的影響，但表現(xiàn)比選擇排序好的多，因為始終都是 O(nlogn) 的時間復雜度。代價是需要額外的內(nèi)存空間
Python3歸并排序-歸并類排序?qū)嵗创a
# 作者：沙振宇
# 歸并排序
def mergeSort(arr):
import math
if(len(arr)<2):
return arr
middle = math.floor(len(arr)/2)
left, right = arr[0:middle], arr[middle:]
return merge(mergeSort(left), mergeSort(right))
def merge(left,right):
result = []
while left and right:
if left[0] <= right[0]:
result.append(left.pop(0))
else:
result.append(right.pop(0))
while left:
result.append(left.pop(0))
while right:
result.append(right.pop(0))
return result
if __name__ == '__main__':
list = [1, 5, 8, 123, 22, 54, 7, 99, 300, 222]
print("List source is:", list)
result = mergeSort(list)
print("List sort is:", result)
效果
8、Python3計數(shù)排序-分布類排序
計數(shù)排序的核心在于將輸入的數(shù)據(jù)值轉(zhuǎn)化為鍵存儲在額外開辟的數(shù)組空間中。
作為一種線性時間復雜度的排序，計數(shù)排序要求輸入的數(shù)據(jù)必須是有確定范圍的整數(shù)。
當輸入的元素是 n 個 0 到 k 之間的整數(shù)時，它的運行時間是 Θ(n + k)。計數(shù)排序不是比較排序，排序的速度快于任何比較排序算法。
由于用來計數(shù)的數(shù)組C的長度取決于待排序數(shù)組中數(shù)據(jù)的范圍（等于待排序數(shù)組的最大值與最小值的差加上1），這使得計數(shù)排序?qū)τ跀?shù)據(jù)范圍很大的數(shù)組，需要大量時間和內(nèi)存。例如：計數(shù)排序是用來排序0到100之間的數(shù)字的最好的算法，但是它不適合按字母順序排序人名。但是，計數(shù)排序可以用在基數(shù)排序中的算法來排序數(shù)據(jù)范圍很大的數(shù)組。
通俗地理解，例如有 10 個年齡不同的人，統(tǒng)計出有 8 個人的年齡比 A 小，那 A 的年齡就排在第 9 位,用這個方法可以得到其他每個人的位置,也就排好了序。當然，年齡有重復時需要特殊處理（保證穩(wěn)定性），這就是為什么最后要反向填充目標數(shù)組，以及將每個數(shù)字的統(tǒng)計減去 1 的原因。
Python3計數(shù)排序-分布類排序?qū)嵗创a
# 作者：沙振宇
# 計數(shù)排序
def countingSort(arr, maxValue):
bucketLen = maxValue+1
bucket = [0]*bucketLen
sortedIndex =0
arrLen = len(arr)
for i in range(arrLen):
if not bucket[arr[i]]:
bucket[arr[i]]=0
bucket[arr[i]]+=1
for j in range(bucketLen):
while bucket[j]>0:
arr[sortedIndex] = j
sortedIndex+=1
bucket[j]-=1
return arr
if __name__ == '__main__':
list = [1, 5, 8, 123, 22, 54, 7, 99, 300, 222]
print("List source is:", list)
result = countingSort(list,max(list))
print("List sort is:", result)
效果
9、Python3基數(shù)排序-分布類排序
基數(shù)排序是一種非比較型整數(shù)排序算法。
其原理是將整數(shù)按位數(shù)切割成不同的數(shù)字，然后按每個位數(shù)分別比較。由于整數(shù)也可以表達字符串（比如名字或日期）和特定格式的浮點數(shù)，所以基數(shù)排序也不是只能使用于整數(shù)。
python3基數(shù)排序-分布類排序?qū)嵗创a
# 作者：沙振宇
# 基數(shù)排序
def radix_sort(arr):
"""基數(shù)排序"""
i = 0 # 記錄當前正在排拿一位，最低位為1
max_num = max(arr) # 最大值
j = len(str(max_num)) # 記錄最大值的位數(shù)
while i < j:
bucket_list =[[] for _ in range(10)] #初始化桶數(shù)組
for x in arr:
bucket_list[int(x / (10**i)) % 10].append(x) # 找到位置放入桶數(shù)組
arr.clear()
for x in bucket_list: # 放回原序列
for y in x:
arr.append(y)
i += 1
return arr
if __name__ == '__main__':
list = [1, 5, 8, 123, 22, 54, 7, 99, 300, 222]
print("List source is:", list)
result = radix_sort(list)
print("List sort is:", result)
效果
Python3桶排序-分布類排序
桶排序是計數(shù)排序的升級版。
它利用了函數(shù)的映射關(guān)系，高效與否的關(guān)鍵就在于這個映射函數(shù)的確定。為了使桶排序更加高效，我們需要做到這兩點：
1、在額外空間充足的情況下，盡量增大桶的數(shù)量
2、使用的映射函數(shù)能夠?qū)⑤斎氲?N 個數(shù)據(jù)均勻的分配到 K 個桶中
同時，對于桶中元素的排序，選擇何種比較排序算法對于性能的影響至關(guān)重要。
最快：當輸入的數(shù)據(jù)可以均勻的分配到每一個桶中。
最慢：當輸入的數(shù)據(jù)被分配到了同一個桶中。
Python3桶排序-分布類排序?qū)嵗创a
# 作者：沙振宇
# 桶排序
def bucketSort(arr):
# 選擇一個最大的數(shù)
max_num = max(arr)
# 創(chuàng)建一個元素全是0的列表, 當做桶
bucket = [0] * (max_num + 1)
# 把所有元素放入桶中, 即把對應(yīng)元素個數(shù)加一
for i in arr:
bucket[i] += 1
# 存儲排序好的元素
sort_nums = []
# 取出桶中的元素
for j in range(len(bucket)):
if bucket[j] != 0:
for y in range(bucket[j]):
sort_nums.append(j)
return sort_nums
if __name__ == '__main__':
list = [1, 5, 8, 123, 22, 54, 7, 99, 300, 222]
print("List source is:", list)
result = bucketSort(list)
print("List sort is:", result)
效果
本文主要講解了10個python3常用排序算法詳細說明與實例，更多關(guān)于python排序算法的知識請查看下面的相關(guān)鏈接
相關(guān)文章
在漏洞利用Python代碼真的很爽...2007-08-08
這篇文章主要介紹了Python函數(shù)參數(shù)操作,結(jié)合實例形式詳細分析了Python形參、實參、默認參數(shù)、關(guān)鍵字參數(shù)、可變參數(shù)、對參數(shù)解包以及獲取參數(shù)個數(shù)等相關(guān)操作技巧,需要的朋友可以參考下2018-08-08
Python+Pygame實戰(zhàn)之實現(xiàn)小蜜蜂歷險記游戲
這篇文章主要為大家介紹了如何利用Python中的Pygame模塊實現(xiàn)小蜜蜂歷險記游戲，文中的示例代碼講解詳細，對我們學習Python游戲開發(fā)有一定幫助，需要的可以參考一下2022-08-08
Python神器之使用watchdog監(jiān)控文件變化
這篇文章主要為大家詳細介紹了Python中的神器watchdog以及如何使用watchdog監(jiān)控文件變化,文中的示例代碼講解詳細,感興趣的小伙伴可以了解下2023-12-12
Python標準庫之循環(huán)器(itertools)介紹
這篇文章主要介紹了Python標準庫之循環(huán)器(itertools)介紹,本文講解了無窮循環(huán)器、函數(shù)式工具、組合工具、groupby()、其它工具等內(nèi)容,需要的朋友可以參考下2014-11-11
Python進程，多進程，獲取進程id，給子進程傳遞參數(shù)操作示例
這篇文章主要介紹了Python進程，多進程，獲取進程id，給子進程傳遞參數(shù)操作,結(jié)合實例形式分析了Python多進程、父子進程以及進程參數(shù)傳遞相關(guān)操作技巧,需要的朋友可以參考下2019-10-10
本文主要介紹了Python中的__new__()方法的使用的基本知識,本文中給出了基于Python2.x的代碼實例,需要的朋友可以參考一下2015-04-04
Python用selenium實現(xiàn)自動登錄和下單的項目實戰(zhàn)
本文主要介紹了Python用selenium實現(xiàn)自動登錄和下單的項目實戰(zhàn)，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2023-02-02
這篇文章主要介紹了Django使用Jinja2模板引擎的示例代碼，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2019-08-08
Pytorch中的Tensorboard與Transforms搭配使用
這篇文章主要介紹了Pytorch中的Tensorboard與Transforms搭配使用，主要是結(jié)合了前兩篇文章的的一個小練習，感興趣的小伙伴可以來練習一下，希望對你的學習有所幫助2021-12-12