【Python】用Python實(shí)現(xiàn)十大經(jīng)典排序算法
來源：Python數(shù)據(jù)之道 (ID:PyDataLab)
作者：陽哥
大家好，我是陽哥。
最近一段時(shí)間，我在微信視頻號(hào)「Python數(shù)據(jù)之道」上陸陸續(xù)續(xù)發(fā)布了10種經(jīng)典排序算法的動(dòng)畫實(shí)現(xiàn)。
今天，想以圖文以及動(dòng)畫的形式，詳細(xì)的跟大家分享下。
10種經(jīng)典排序算法包括冒泡排序、選擇排序、快速排序、歸并排序、堆排序、插入排序、希爾排序、計(jì)數(shù)排序、桶排序、基數(shù)排序等。
當(dāng)然，還有一些其他的排序算法，大家可以繼續(xù)去研究下。
01冒泡排序
冒泡排序（Bubble Sort）是一種比較簡(jiǎn)單的排序算法，它重復(fù)地走訪過要排序的元素，依次比較相鄰兩個(gè)元素，如果它們的順序錯(cuò)誤就把他們調(diào)換過來，直到?jīng)]有元素再需要交換，排序完成。
注：上圖中，數(shù)字表示的是數(shù)據(jù)序列原始的索引號(hào)。
算法過程
比較相鄰的元素，如果前一個(gè)比后一個(gè)大，就把它們兩個(gè)對(duì)調(diào)位置。
對(duì)排序數(shù)組中每一對(duì)相鄰元素做同樣的工作，直到全部完成，此時(shí)最后的元素將會(huì)是本輪排序中最大的數(shù)。
對(duì)剩下的元素繼續(xù)重復(fù)以上的步驟，直到?jīng)]有任何一個(gè)元素需要比較。
冒泡排序每次找出一個(gè)最大的元素，因此需要遍歷 n-1 次 （n為數(shù)據(jù)序列的長(zhǎng)度）。
算法特點(diǎn)
什么時(shí)候最快（Best Cases）：當(dāng)輸入的數(shù)據(jù)已經(jīng)是正序時(shí)。
什么時(shí)候最慢（Worst Cases）：當(dāng)輸入的數(shù)據(jù)是反序時(shí)。
Python代碼
def?bubble_sort(lst):
????n?=?len(lst)
????for?i?in?range(n):
????????for?j?in?range(1,?n?-?i):
????????????if?lst[j?-?1]?>?lst[j]:
????????????????lst[j?-?1],?lst[j]?=?lst[j],?lst[j?-?1]
????return?lst
算法動(dòng)畫演示
冒泡排序的動(dòng)態(tài)演示如下：
02選擇排序
選擇排序原理
選擇排序（Selection Sort）的原理，每一輪從待排序的記錄中選出最小的元素，存放在序列的起始位置，然后再從剩余的未排序元素中尋找到最小元素，然后放到已排序的序列的末尾。以此類推，直到全部待排序的數(shù)據(jù)元素的個(gè)數(shù)為零。得到數(shù)值從小到達(dá)排序的數(shù)據(jù)序列。
也可以每一輪找出數(shù)值最大的元素，這樣的話，排序完畢后的數(shù)組最終是從大到小排列。
選擇排序每次選出最?。ㄗ畲螅┑脑?，因此需要遍歷 n-1 次。
Python代碼
def?selection_sort(lst):
????for?i?in?range(len(lst)?-?1):??
????????min_index?=?i
????????for?j?in?range(i?+?1,?len(lst)):
????????????if?lst[j]?????????????????min_index?=?j??
????????lst[i],?lst[min_index]?=?lst[min_index],?lst[i]?
????return?lst
算法動(dòng)畫演示
選擇排序的動(dòng)態(tài)演示如下：
03快速排序
快速排序（Quick Sort），是在上世紀(jì)60年代，由美國人東尼·霍爾提出的一種排序方法。這種排序方式，在當(dāng)時(shí)已經(jīng)是非常快的一種排序了。因此在命名上，才將之稱為“快速排序”。
算法過程
先從數(shù)據(jù)序列中取出一個(gè)數(shù)作為基準(zhǔn)數(shù)（baseline，習(xí)慣取第一個(gè)數(shù)）。 分區(qū)過程，將比基準(zhǔn)數(shù)小的數(shù)全放到它的左邊,大于或等于它的數(shù)全放到它的右邊。 再對(duì)左右區(qū)間遞歸(recursive)重復(fù)第二步，直到各區(qū)間只有一個(gè)數(shù)。
因?yàn)閿?shù)據(jù)序列之間的順序都是固定的。最后將這些子序列一次組合起來，整體的排序就完成了。
如下圖，對(duì)于數(shù)據(jù)序列，先取第一個(gè)數(shù)據(jù) 15為基準(zhǔn)數(shù)，將比 15 小的數(shù)放在左邊，比 15 大（大于或等于）的數(shù)放在右邊
接下來，對(duì)于左邊部分，重復(fù)上面的步驟，如下圖，取左邊序列的第一個(gè)數(shù)據(jù) 11 為基準(zhǔn)數(shù)，將比 11 小的數(shù)放在左邊，比 11 大（大于或等于）的數(shù)放在右邊。
繼續(xù)遞歸重復(fù)上述過程，直到每個(gè)區(qū)間只有一個(gè)數(shù)。這樣就會(huì)完成排序
Python代碼
def?quick_sort(lst):??
????n?=?len(lst)
????if?n?<=?1:
????????return?lst
????baseline?=?lst[0]?
????left?=?[lst[i]?for?i?in?range(1,?len(lst))?if?lst[i]?????right?=?[lst[i]?for?i?in?range(1,?len(lst))?if?lst[i]?>=?baseline]
????return?quick_sort(left)?+?[baseline]?+?quick_sort(right)
算法動(dòng)畫演示
快速排序的動(dòng)態(tài)演示如下：
04歸并排序
算法思想
歸并排序（Merge Sort）是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法的一個(gè)非常典型的應(yīng)用，歸并排序?qū)蓚€(gè)已經(jīng)有序的子序列合并成一個(gè)有序的序列。
算法流程
主要兩步(拆分，合并)
步驟１：進(jìn)行序列拆分，一直拆分到只有一個(gè)元素； 步驟２：拆分完成后，開始遞歸合并。
思路：假設(shè)我們有一個(gè)沒有排好序的序列，那么我們首先使用拆分的方法將這個(gè)序列分割成一個(gè)個(gè)已經(jīng)排好序的子序列（直到剩下一個(gè)元素）。然后再利用歸并方法將一個(gè)個(gè)有序的子序列合并成排好序的序列。
圖解算法
拆分
對(duì)于數(shù)據(jù)序列 [15,11,13,18,10] ,我們從首先從數(shù)據(jù)序列的中間位置開始拆分，中間位置的設(shè)置為
首次拆分如下：
第一次拆分后，依次對(duì)子序列進(jìn)行拆分，拆分過程如下：
合并
合并過程中，對(duì)于左右分區(qū)以及其子區(qū)間，遞歸使用合并方法。先從左邊最小的子區(qū)間開始，對(duì)于每個(gè)區(qū)間，依次將最小的數(shù)據(jù)放在最左邊，然后對(duì)右邊區(qū)間也執(zhí)行同樣的操作。
合并過程的完整圖示如下：
Python代碼
def?merge_sort(lst):
????def?merge(left,right):
????????i?=?0
????????j?=?0???
????????result?=?[]????
????????while?i?and?j?????????????if?left[i]?<=?right[j]:????
????????????????result.append(left[i])
????????????????i?+=?1
????????????else:
????????????????result.append(right[j])
????????????????j?+=?1
????????result?=?result?+?left[i:]?+?right[j:]
????????return?result
????n?=?len(lst)
????if?n?<=?1:?????
????????return?lst?
????mid?=?n?//?2?
????left?=?merge_sort(lst[:mid])
????right?=?merge_sort(lst[mid:])
????return?merge(left,right)
算法動(dòng)畫演示
歸并排序的動(dòng)態(tài)演示如下：
05堆排序
要理解堆排序（Heap Sort）算法，首先要知道什么是“堆”。
堆的定義
對(duì)于 n 個(gè)元素的數(shù)據(jù)序列 ，當(dāng)且僅當(dāng)滿足下列情形之一時(shí)，才稱之為 堆:
情形1：
情形2：
若序列 是堆，則堆頂元素必為序列中n個(gè)元素的最小值或最大值。
小頂堆如下圖所示：
大頂堆如下圖所示：
若在輸出堆頂?shù)淖钚≈担ɑ蜃畲笾担┲螅沟檬Ｓ鄋-1個(gè)元素的序列重又建成一個(gè)堆，則得到n個(gè)元素的次小值（或次大值）。如此反復(fù)執(zhí)行，便能得到一個(gè)有序序列，這個(gè)過程稱之為 堆排序。
堆的存儲(chǔ)
一般用數(shù)組來表示堆，若根結(jié)點(diǎn)存在序號(hào) 0 處， i 結(jié)點(diǎn)的父結(jié)點(diǎn)下標(biāo)就為 (i-1)/2。i 結(jié)點(diǎn)的左右子結(jié)點(diǎn)下標(biāo)分別為 2*i+1和 2*i+2 。
對(duì)于上面提到的小頂堆和大頂堆，其數(shù)據(jù)存儲(chǔ)情況如下：
每幅圖的右邊為其數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)，左邊為其邏輯結(jié)構(gòu)。
堆排序
實(shí)現(xiàn)堆排序需要解決兩個(gè)問題：
如何由一個(gè)無序序列建成一個(gè)堆？
如何在輸出堆頂元素之后，調(diào)整剩余元素成為一個(gè)新的堆？
堆的初始化
第一個(gè)問題實(shí)際上就是堆的初始化，下面來闡述下如何構(gòu)造初始堆，假設(shè)初始的數(shù)據(jù)序列如下：
咱們首先需要將其以樹形結(jié)構(gòu)來展示，如下：
初始化堆的時(shí)候是對(duì)所有的非葉子結(jié)點(diǎn)進(jìn)行篩選。
最后一個(gè)非終端元素的下標(biāo)是 [n/2] 向下取整，所以篩選只需要從第 [n/2] 向下取整個(gè)元素開始，從后往前進(jìn)行調(diào)整。
從最后一個(gè)非葉子結(jié)點(diǎn)開始，每次都是從父結(jié)點(diǎn)、左邊子節(jié)點(diǎn)、右邊子節(jié)點(diǎn)中進(jìn)行比較交換，交換可能會(huì)引起子結(jié)點(diǎn)不滿足堆的性質(zhì)，所以每次交換之后需要重新對(duì)被交換的子結(jié)點(diǎn)進(jìn)行調(diào)整。
以小頂堆為例，構(gòu)造初始堆的過程如下：
進(jìn)行堆排序
有了初始堆之后就可以進(jìn)行排序了。
堆排序是一種選擇排序。建立的初始堆為初始的無序區(qū)。
排序開始，首先輸出堆頂元素（因?yàn)樗亲钪担?，將堆頂元素和最后一個(gè)元素交換，這樣，第n個(gè)位置（即最后一個(gè)位置）作為有序區(qū)，前n-1個(gè)位置仍是無序區(qū)，對(duì)無序區(qū)進(jìn)行調(diào)整，得到堆之后，再交換堆頂和最后一個(gè)元素，這樣有序區(qū)長(zhǎng)度變?yōu)?。。。
不斷進(jìn)行此操作，將剩下的元素重新調(diào)整為堆，然后輸出堆頂元素到有序區(qū)。每次交換都導(dǎo)致無序區(qū)-1，有序區(qū)+1。不斷重復(fù)此過程直到有序區(qū)長(zhǎng)度增長(zhǎng)為n-1，排序完成。
對(duì)于堆初始化，以及堆排序，最好還是通過視頻演示來理解，這樣更直觀。
堆排序的動(dòng)態(tài)演示如下：
Python代碼
def?heap_sort(lst):
????def?adjust_heap(lst,?i,?size):
????????left_index?=?2?*?i?+?1
????????right_index?=?2?*?i?+?2
????????largest_index?=?i?
????????if?left_index?and?lst[left_index]?>?lst[largest_index]:?
????????????largest_index?=?left_index?
????????if?right_index?and?lst[right_index]?>?lst[largest_index]:?
????????????largest_index?=?right_index?
????????if?largest_index?!=?i:?
????????????lst[largest_index],?lst[i]?=?lst[i],?lst[largest_index]?
????????????adjust_heap(lst,?largest_index,?size)
????def?built_heap(lst,?size):
????????for?i?in?range(len(lst)//2)[::-1]:?
????????????adjust_heap(lst,?i,?size)?
????size?=?len(lst)
????built_heap(lst,?size)?
????for?i?in?range(len(lst))[::-1]:?????????
????????lst[0],?lst[i]?=?lst[i],?lst[0]
????????adjust_heap(lst,?0,?i)?
????return?lst
06插入排序
插入排序(Insertion Sort)就是每一步都將一個(gè)需要排序的數(shù)據(jù)按其大小插入到已經(jīng)排序的數(shù)據(jù)序列中的適當(dāng)位置，直到全部插入完畢。
插入排序如同打撲克牌一樣，每次將后面的牌插到前面已經(jīng)排好序的牌中。
Python代碼
def?insertion_sort(lst):
????for?i?in?range(len(lst)?-?1):
????????cur_num,?pre_index?=?lst[i+1],?i
????????while?pre_index?>=?0?and?cur_num?????????????lst[pre_index?+?1]?=?lst[pre_index]
????????????pre_index?-=?1
????????lst[pre_index?+?1]?=?cur_num?
????return?lst
算法動(dòng)畫演示
插入排序的動(dòng)態(tài)演示如下：
07希爾排序
基本原理
希爾排序(Shell Sort)是插入排序的一種更高效率的實(shí)現(xiàn)。
希爾排序的核心在于間隔序列的設(shè)定。既可以提前設(shè)定好間隔序列，也可以動(dòng)態(tài)的定義間隔序列。
這里以動(dòng)態(tài)間隔序列為例來描述。初始間隔（gap值）為數(shù)據(jù)序列長(zhǎng)度除以2取整，后續(xù)間隔以 前一個(gè)間隔數(shù)值除以2取整為循環(huán)，直到最后一個(gè)間隔值為 1 。
對(duì)于下面這個(gè)數(shù)據(jù)序列，初始間隔數(shù)值為5
先將數(shù)據(jù)序列按間隔進(jìn)行子序列分組，第一個(gè)子序列的索引為[0,5,10]，這里分成了5組。
為方便大家區(qū)分不同的子序列，對(duì)同一個(gè)子序列標(biāo)注相同的顏色，分組情況如下：
分組結(jié)束后，子序列內(nèi)部進(jìn)行插入排序，gap為5的子序列內(nèi)部排序后如下：
注：紅色箭頭標(biāo)注的地方，是子序列內(nèi)部排序后的狀態(tài)
接下來選取第二個(gè)間隔值，按照間隔值進(jìn)行子序列分組，同樣地，子序列內(nèi)部分別進(jìn)行插入排序；
如果數(shù)據(jù)序列比較長(zhǎng)，則會(huì)選取第3個(gè)、第4個(gè)或者更多個(gè)間隔值，重復(fù)上述的步驟。
gap為2的排序情況前后對(duì)照如下：
最后一個(gè)間隔值為1，這一次相當(dāng)于簡(jiǎn)單的插入排序。但是經(jīng)過前幾次排序，序列已經(jīng)基本有序，因此最后一次排序時(shí)間效率就提高了很多。
Python代碼
def?shell_sort(lst):
????n?=?len(lst)
????gap?=?n?//?2
????while?gap?>?0:
????????for?i?in?range(gap,?n):
????????????for?j?in?range(i,?gap?-?1,?-gap):
????????????????if?lst[j]?????????????????????lst[j],?lst[j?-?gap]?=?lst[j?-?gap],?lst[j]
????????????????else:
????????????????????break
????????gap?//=?2
????return?lst
算法動(dòng)畫演示
希爾排序的動(dòng)態(tài)演示如下：
08計(jì)數(shù)排序
基本原理
計(jì)數(shù)排序（Counting Sort）的核心在于將輸入的數(shù)據(jù)值轉(zhuǎn)化為鍵，存儲(chǔ)在額外開辟的數(shù)組空間中。計(jì)數(shù)排序要求輸入的數(shù)據(jù)必須是有確定范圍的整數(shù)。
算法的步驟如下：
先找出待排序的數(shù)組中最大和最小的元素，新開辟一個(gè)長(zhǎng)度為 最大值-最小值+1 的數(shù)組；
然后，統(tǒng)計(jì)原數(shù)組中每個(gè)元素出現(xiàn)的次數(shù)，存入到新開辟的數(shù)組中；
接下來，根據(jù)每個(gè)元素出現(xiàn)的次數(shù)，按照新開辟數(shù)組中從小到大的秩序，依次填充到原來待排序的數(shù)組中，完成排序。
Python代碼
def?counting_sort(lst):
????nums_min?=?min(lst)
????bucket?=?[0]?*?(max(lst)?+?1?-?nums_min)
????for?num?in?lst:
????????bucket[num?-?nums_min]?+=?1
????i?=?0
????for?j?in?range(len(bucket)):
????????while?bucket[j]?>?0:
????????????lst[i]?=?j?+?nums_min
????????????bucket[j]?-=?1
????????????i?+=?1
????return?lst
算法動(dòng)畫演示
計(jì)數(shù)排序的動(dòng)態(tài)演示如下：
09桶排序
基本思想
簡(jiǎn)單來說，桶排序（Bucket Sort）就是把數(shù)據(jù)分組，放在一個(gè)個(gè)的桶中，對(duì)每個(gè)桶里面的數(shù)據(jù)進(jìn)行排序，然后將桶進(jìn)行數(shù)據(jù)合并，完成桶排序。
該算法分為四步，包括劃分桶、數(shù)據(jù)入桶、桶內(nèi)排序、數(shù)據(jù)合并。
桶的劃分過程
這里詳細(xì)介紹下桶的劃分過程。
對(duì)于一個(gè)數(shù)值范圍在10到 49范圍內(nèi)的數(shù)組，我們?nèi)⊥暗拇笮?0 （defaultBucketSize = 10），則第一個(gè)桶的范圍為 10到20，第二個(gè)桶的數(shù)據(jù)范圍是20到30，依次類推。最后，我們一共需要4個(gè)桶來放入數(shù)據(jù)。
排序過程
對(duì)于下面這個(gè)數(shù)據(jù)序列，初始設(shè)定桶的大小為 20 （defaultBucketSize = 20），經(jīng)計(jì)算，一共需要4個(gè)桶來放入數(shù)據(jù)。
然后將原始數(shù)組按數(shù)值大小放入到對(duì)應(yīng)的桶中，完成數(shù)據(jù)分組。
對(duì)于桶內(nèi)的數(shù)據(jù)序列，這時(shí)可以用冒泡排序、選擇排序等多種排序算法來對(duì)數(shù)據(jù)進(jìn)行排序。這些算法，在之前的視頻里已有介紹，大家可以去了解下。
這里，我選用 冒泡排序 來對(duì)桶內(nèi)數(shù)據(jù)進(jìn)行排序。
桶內(nèi)排序完成后，將數(shù)據(jù)按桶的順序進(jìn)行合并，這樣就得到所有數(shù)值排好序的數(shù)據(jù)序列了
詳細(xì)的動(dòng)畫演示過程如下：
Python代碼
def?bucket_sort(lst,?defaultBucketSize=4):
????maxVal,?minVal?=?max(lst),?min(lst)
????bucketSize?=?defaultBucketSize
????bucketCount?=?(maxVal?-?minVal)?//?bucketSize?+?1??
????buckets?=?[[]?for?i?in?range(bucketCount)]
????for?num?in?lst:
????????buckets[(num?-?minVal)?//?bucketSize].append(num)
????lst.clear()??
????for?bucket?in?buckets:
????????bubble_sort(bucket)??
????????lst.extend(bucket)
????return?lst
10基數(shù)排序
基數(shù)排序（radix sort）屬于“分配式排序”（distribution sort），它是透過鍵值的部份信息，將要排序的元素分配至某些“桶”中，以達(dá)到排序的作用。
基數(shù)排序適用于所有元素均為正整數(shù)的數(shù)組。
基本思想
排序過程分為“分配”和“收集”。
排序過程中，將元素分層為多個(gè)關(guān)鍵碼進(jìn)行排序（一般按照數(shù)值的個(gè)位、十位、百位、…… 進(jìn)行區(qū)分），多關(guān)鍵碼排序按照從最主位關(guān)鍵碼到最次位關(guān)鍵碼或從最次位到最主位關(guān)鍵碼的順序逐次排序。
基數(shù)排序的方式可以采用最低位優(yōu)先LSD（Least sgnificant digital）法或最高位優(yōu)先MSD（Most sgnificant digital）法，LSD的排序方式由鍵值的最右邊開始，而MSD則相反，由鍵值的最左邊開始。
LSD的基數(shù)排序適用于位數(shù)小的數(shù)列，如果位數(shù)多的話，使用MSD的效率會(huì)比較好，MSD的方式恰與LSD相反，是由高位數(shù)為基底開始進(jìn)行分配，其他的演算方式則都相同。
算法流程
這里以最低位優(yōu)先LSD為例。
先根據(jù)個(gè)位數(shù)的數(shù)值，在掃描數(shù)值時(shí)將它們分配至編號(hào)0到9的桶中，然后將桶子中的數(shù)值串接起來。
將這些桶子中的數(shù)值重新串接起來，成為新的序列，接著再進(jìn)行一次分配，這次是根據(jù)十位數(shù)來分配。
如果排序的對(duì)象有三位數(shù)以上，則持續(xù)進(jìn)行以上的動(dòng)作直至最高位數(shù)為止。
詳細(xì)的動(dòng)畫演示過程如下：
Python代碼
#?LSD?Radix?Sort
def?radix_sort(lst):
????mod?=?10
????div?=?1
????mostBit?=?len(str(max(lst)))?
????buckets?=?[[]?for?row?in?range(mod)]?
????while?mostBit:
????????for?num?in?lst:??
????????????buckets[num?//?div?%?mod].append(num)
????????i?=?0??
????????for?bucket?in?buckets:??
????????????while?bucket:
????????????????lst[i]?=?bucket.pop(0)
????????????????i?+=?1
????????div?*=?10
????????mostBit?-=?1
????return?lst
11小結(jié)
以上就是用 Python 來實(shí)現(xiàn)10種經(jīng)典排序算法的相關(guān)內(nèi)容。
對(duì)于這些排序算法的實(shí)現(xiàn)，代碼其實(shí)并不是最主要的，重要的是需要去理解各種算法的基本思想、基本原理以及其內(nèi)部的實(shí)現(xiàn)過程。
對(duì)于每種算法，用其他編程語言同樣是可以去實(shí)現(xiàn)的。
并且，對(duì)于同一種算法，即使只用 Python 語言，也有多種不同的代碼方式可以來實(shí)現(xiàn)，但其基本原理是一致的。
對(duì)于本篇文章分享的內(nèi)容，對(duì)于我自己而言，最難的還是以動(dòng)畫的形式，將這些算法的原理實(shí)現(xiàn)出來。
如果大家覺得這種形式不錯(cuò)，我也會(huì)考慮以這種形式分享一些其他相關(guān)的內(nèi)容。
BTW，在微信視頻號(hào)「Python數(shù)據(jù)之道」發(fā)布這些算法動(dòng)畫視頻的過程中，不少同學(xué)都在問我這些視頻是怎么做的，用什么工具做的，…… ，諸如此類的問題。
如果本篇文章 “在看” 數(shù)量超過 100 個(gè)的話，我會(huì)考慮來介紹這些動(dòng)畫視頻是怎么做的哈。
參考文檔
https://www.jianshu.com/p/bbbab7fa77a2 https://blog.csdn.net/MakerCloud/article/details/86182145 https://www.cnblogs.com/mengdd/archive/2012/11/30/2796845.html https://www.cnblogs.com/jin-nuo/p/5293554.html
大家讀完順手點(diǎn)下右下角的 ?“在看” ，就是最大的鼓勵(lì)和支持了。
往期精彩回顧 本站qq群955171419，加入微信群請(qǐng)掃碼：