（附代碼）動圖圖解 | 十大經(jīng)典排序算法Python版實現(xiàn)
點擊左上方藍字關(guān)注我們
轉(zhuǎn)載自 | 機器學習算法那些事
平方階 (O(n2)) 排序：各類簡單排序，直接插入、直接選擇和冒泡排序； 線性對數(shù)階 (O(nlog2n)) 排序：快速排序、堆排序和歸并排序； 希爾排序：O(n1+§)) 排序，§ 是介于 0 和 1 之間的常數(shù)； 線性階 (O(n)) 排序：基數(shù)排序，此外還有桶、箱排序。
排序后 2 個相等鍵值的順序和排序之前它們的順序相同。
穩(wěn)定的排序算法：冒泡排序、插入排序、歸并排序和基數(shù)排序。
不是穩(wěn)定的排序算法：選擇排序、快速排序、希爾排序、堆排序。
n：數(shù)據(jù)規(guī)模。
k：“桶”的個數(shù)。
In-place：占用常數(shù)內(nèi)存，不占用額外內(nèi)存。
Out-place：占用額外內(nèi)存。
1. 算法步驟
比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。 對每一對相鄰元素作同樣的工作，從開始第一對到結(jié)尾的最后一對。這步做完后，最后的元素會是最大的數(shù)。 針對所有的元素重復以上的步驟，除了最后一個。 持續(xù)每次對越來越少的元素重復上面的步驟，直到?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
1. 算法步驟
首先在未排序序列中找到最?。ù螅┰?，存放到排序序列的起始位置。 再從剩余未排序元素中繼續(xù)尋找最?。ù螅┰兀缓蠓诺揭雅判蛐蛄械哪┪?。 重復第二步，直到所有元素均排序完畢。
def selectionSort(arr):for i in range(len(arr) - 1):# 記錄最小數(shù)的索引minIndex = ifor 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
1. 算法步驟
將第一待排序序列第一個元素看做一個有序序列，把第二個元素到最后一個元素當成是未排序序列。 從頭到尾依次掃描未排序序列，將掃描到的每個元素插入有序序列的適當位置。（如果待插入的元素與有序序列中的某個元素相等，則將待插入元素插入到相等元素的后面。）
def insertionSort(arr):for i in range(len(arr)):preIndex = i-1current = arr[i]while preIndex >= 0 and arr[preIndex] > current:arr[preIndex+1] = arr[preIndex]preIndex-=1arr[preIndex+1] = currentreturn arr
插入排序在對幾乎已經(jīng)排好序的數(shù)據(jù)操作時，效率高，即可以達到線性排序的效率； 但插入排序一般來說是低效的，因為插入排序每次只能將數(shù)據(jù)移動一位。
1. 算法步驟
選擇一個增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1； 按增量序列個數(shù) k，對序列進行 k 趟排序； 每趟排序，根據(jù)對應的增量 ti，將待排序列分割成若干長度為 m 的子序列，分別對各子表進行直接插入排序。僅增量因子為 1 時，整個序列作為一個表來處理，表長度即為整個序列的長度。
def shellSort(arr):import mathgap=1< len(arr)/3):gap = gap*3+1while gap > 0:for i in range(gap,len(arr)):temp = arr[i]j = i-gapwhile j >=0 and arr[j] > temp:=arr[j]=gap= tempgap = math.floor(gap/3)return arr}
自上而下的遞歸（所有遞歸的方法都可以用迭代重寫，所以就有了第 2 種方法）； 自下而上的迭代。
1. 算法步驟
申請空間，使其大小為兩個已經(jīng)排序序列之和，該空間用來存放合并后的序列； 設定兩個指針，最初位置分別為兩個已經(jīng)排序序列的起始位置； 比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置； 重復步驟 3 直到某一指針達到序列尾； 將另一序列剩下的所有元素直接復制到合并序列尾。
def mergeSort(arr):import mathif(len(arr)<2):return arrmiddle = 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
快速排序的最壞運行情況是 O(n2)，比如說順序數(shù)列的快排。但它的平攤期望時間是 O(nlogn)，且 O(nlogn) 記號中隱含的常數(shù)因子很小，比復雜度穩(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 leftright = len(arr)-1 if not isinstance(right,(int, float)) else rightif 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 = leftindex = pivot+1i = indexwhile i <= right:if arr[i] < arr[pivot]:swap(arr, i, index)index+=1i+=1swap(arr,pivot,index-1)return index-1def 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)整到相應位置； 重復步驟 2，直到堆的尺寸為 1。
def buildMaxHeap(arr):import mathfor i in range(math.floor(len(arr)/2),-1,-1):heapify(arr,i)def heapify(arr, i):left = 2*i+1right = 2*i+2largest = iif left < arrLen and arr[left] > arr[largest]:largest = leftif right < arrLen and arr[right] > arr[largest]:largest = rightif 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 arrLenarrLen = len(arr)buildMaxHeap(arr)for i in range(len(arr)-1,0,-1):swap(arr,0,i)arrLen -=1heapify(arr, 0)return arr
def countingSort(arr, maxValue):bucketLen = maxValue+1bucket = [0]*bucketLensortedIndex =0arrLen = len(arr)for i in range(arrLen):if not bucket[arr[i]]:bucket[arr[i]]=0bucket[arr[i]]+=1for j in range(bucketLen):while bucket[j]>0:arr[sortedIndex] = jsortedIndex+=1bucket[j]-=1return arr
在額外空間充足的情況下，盡量增大桶的數(shù)量。 使用的映射函數(shù)能夠?qū)⑤斎氲?N 個數(shù)據(jù)均勻的分配到 K 個桶中。
什么時候最快
什么時候最慢
Python 代碼
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)用了sortedfor 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]
1. 基數(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 += 1while 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) #將對應的數(shù)組元素加入到相 #應位基數(shù)的桶中j = 0for k in range(10):if len(bucket[k]) != 0: #若桶不為空for y in bucket[k]: #將該桶中每個元素list[j] = y #放回到數(shù)組中j += 1i += 1return list
END
雙一流大學研究生團隊創(chuàng)建，專注于目標檢測與深度學習，希望可以將分享變成一種習慣！ 整理不易，點贊三連↓
評論
圖片
表情