全面講解十大經(jīng)典排序算法（Python實現(xiàn)）
點擊上方“小白學(xué)視覺”，選擇加"星標(biāo)"或“置頂”
重磅干貨，第一時間送達
作者 | hustcc
鏈接 | https://github.com/hustcc/JS-Sorting-Algorith
平方階 (O(n2)) 排序 各類簡單排序：直接插入、直接選擇和冒泡排序。 線性對數(shù)階 (O(nlog2n)) 排序 快速排序、堆排序和歸并排序； O(n1+§)) 排序，§ 是介于 0 和 1 之間的常數(shù)。希爾排序 線性階 (O(n)) 排序 基數(shù)排序，此外還有桶、箱排序。
排序后 2 個相等鍵值的順序和排序之前它們的順序相同 穩(wěn)定的排序算法：冒泡排序、插入排序、歸并排序和基數(shù)排序。 不是穩(wěn)定的排序算法：選擇排序、快速排序、希爾排序、堆排序。
1、冒泡排序
（1）算法步驟
比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。 對每一對相鄰元素作同樣的工作，從開始第一對到結(jié)尾的最后一對。這步做完后，最后的元素會是最大的數(shù)。 針對所有的元素重復(fù)以上的步驟，除了最后一個。 持續(xù)每次對越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較。
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
2、選擇排序
（1）算法步驟
首先在未排序序列中找到最?。ù螅┰兀娣诺脚判蛐蛄械钠鹗嘉恢?/span> 再從剩余未排序元素中繼續(xù)尋找最?。ù螅┰?，然后放到已排序序列的末尾。 重復(fù)第二步，直到所有元素均排序完畢。
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
3、插入排序
（1）算法步驟
將第一待排序序列第一個元素看做一個有序序列，把第二個元素到最后一個元素當(dāng)成是未排序序列。 從頭到尾依次掃描未排序序列，將掃描到的每個元素插入有序序列的適當(dāng)位置。（如果待插入的元素與有序序列中的某個元素相等，則將待插入元素插入到相等元素的后面。）
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
4、希爾排序
插入排序在對幾乎已經(jīng)排好序的數(shù)據(jù)操作時，效率高，即可以達到線性排序的效率； 但插入排序一般來說是低效的，因為插入排序每次只能將數(shù)據(jù)移動一位；
（1）算法步驟
選擇一個增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1； 按增量序列個數(shù) k，對序列進行 k 趟排序； 每趟排序，根據(jù)對應(yīng)的增量 ti，將待排序列分割成若干長度為 m 的子序列，分別對各子表進行直接插入排序。僅增量因子為 1 時，整個序列作為一個表來處理，表長度即為整個序列的長度。
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
}
自上而下的遞歸（所有遞歸的方法都可以用迭代重寫，所以就有了第 2 種方法） 自下而上的迭代
（1）算法步驟
申請空間，使其大小為兩個已經(jīng)排序序列之和，該空間用來存放合并后的序列； 設(shè)定兩個指針，最初位置分別為兩個已經(jīng)排序序列的起始位置； 比較兩個指針?biāo)赶虻脑?，選擇相對小的元素放入到合并空間，并移動指針到下一位置； 重復(fù)步驟 3 直到某一指針達到序列尾； 將另一序列剩下的所有元素直接復(fù)制到合并序列尾。
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
6、快速排序
快速排序的最壞運行情況是 O(n2)，比如說順序數(shù)列的快排。但它的平攤期望時間是 O(nlogn)，且 O(nlogn) 記號中隱含的常數(shù)因子很小，比復(fù)雜度穩(wěn)定等于 O(nlogn) 的歸并排序要小很多。所以，對絕大多數(shù)順序性較弱的隨機數(shù)列而言，快速排序總是優(yōu)于歸并排序。
（1）算法步驟
從數(shù)列中挑出一個元素，稱為 “基準”（pivot）; 重新排序數(shù)列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面（相同的數(shù)可以到任一邊）。在這個分區(qū)退出之后，該基準就處于數(shù)列的中間位置。這個稱為分區(qū)（partition）操作； 遞歸地（recursive）把小于基準值元素的子數(shù)列和大于基準值元素的子數(shù)列排序；
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]
大頂堆：每個節(jié)點的值都大于或等于其子節(jié)點的值，在堆排序算法中用于升序排列； 小頂堆：每個節(jié)點的值都小于或等于其子節(jié)點的值，在堆排序算法中用于降序排列；
（1）算法步驟
創(chuàng)建一個堆 H[0……n-1]； 把堆首（最大值）和堆尾互換； 把堆的尺寸縮小 1，并調(diào)用 shift_down(0)，目的是把新的數(shù)組頂端數(shù)據(jù)調(diào)整到相應(yīng)位置； 重復(fù)步驟 2，直到堆的尺寸為 1。
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
8、計數(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
9、桶排序
在額外空間充足的情況下，盡量增大桶的數(shù)量 使用的映射函數(shù)能夠?qū)⑤斎氲?N 個數(shù)據(jù)均勻的分配到 K 個桶中
def bucket_sort(s):
"""桶排序"""
min_num = min(s)
max_num = max(s)
# 桶的大小
bucket_range = (max_num-min_num) / len(s)
# 桶數(shù)組
count_list = [ [] for i in range(len(s) + 1)]
# 向桶數(shù)組填數(shù)
for i in s:
count_list[int((i-min_num)//bucket_range)].append(i)
s.clear()
# 回填，這里桶內(nèi)部排序直接調(diào)用了sorted
for i in count_list:
for j in sorted(i):
s.append(j)
if __name__ == __main__ :
a = [3.2,6,8,4,2,6,7,3]
bucket_sort(a)
print(a) # [2, 3, 3.2, 4, 6, 6, 7, 8]
10、基數(shù)排序
基數(shù)排序 vs 計數(shù)排序 vs 桶排序
基數(shù)排序：根據(jù)鍵值的每位數(shù)字來分配桶； 計數(shù)排序：每個桶只存儲單一鍵值； 桶排序：每個桶存儲一定范圍的數(shù)值；
def RadixSort(list):
i = 0 #初始為個位排序
n = 1 #最小的位數(shù)置為1（包含0）
max_num = max(list) #得到帶排序數(shù)組中最大數(shù)
while max_num > 10**n: #得到最大數(shù)是幾位數(shù)
n += 1
while i < n:
bucket = {} #用字典構(gòu)建桶
for x in range(10):
bucket.setdefault(x, []) #將每個桶置空
for x in list: #對每一位進行排序
radix =int((x / (10**i)) % 10) #得到每位的基數(shù)
bucket[radix].append(x) #將對應(yīng)的數(shù)組元素加入到相 #應(yīng)位基數(shù)的桶中
j = 0
for k in range(10):
if len(bucket[k]) != 0: #若桶不為空
for y in bucket[k]: #將該桶中每個元素
list[j] = y #放回到數(shù)組中
j += 1
i += 1
return list
好消息！
小白學(xué)視覺知識星球
開始面向外開放啦??????
下載1：OpenCV-Contrib擴展模塊中文版教程 在「小白學(xué)視覺」公眾號后臺回復(fù)：擴展模塊中文教程，即可下載全網(wǎng)第一份OpenCV擴展模塊教程中文版，涵蓋擴展模塊安裝、SFM算法、立體視覺、目標(biāo)跟蹤、生物視覺、超分辨率處理等二十多章內(nèi)容。 下載2：Python視覺實戰(zhàn)項目52講 在「小白學(xué)視覺」公眾號后臺回復(fù)：Python視覺實戰(zhàn)項目，即可下載包括圖像分割、口罩檢測、車道線檢測、車輛計數(shù)、添加眼線、車牌識別、字符識別、情緒檢測、文本內(nèi)容提取、面部識別等31個視覺實戰(zhàn)項目，助力快速學(xué)校計算機視覺。 下載3：OpenCV實戰(zhàn)項目20講 在「小白學(xué)視覺」公眾號后臺回復(fù)：OpenCV實戰(zhàn)項目20講，即可下載含有20個基于OpenCV實現(xiàn)20個實戰(zhàn)項目，實現(xiàn)OpenCV學(xué)習(xí)進階。 交流群
歡迎加入公眾號讀者群一起和同行交流，目前有SLAM、三維視覺、傳感器、自動駕駛、計算攝影、檢測、分割、識別、醫(yī)學(xué)影像、GAN、算法競賽等微信群（以后會逐漸細分），請掃描下面微信號加群，備注：”昵稱+學(xué)校/公司+研究方向“，例如：”張三 + 上海交大 + 視覺SLAM“。請按照格式備注，否則不予通過。添加成功后會根據(jù)研究方向邀請進入相關(guān)微信群。請勿在群內(nèi)發(fā)送廣告，否則會請出群，謝謝理解~
評論
圖片
表情