來源：Python數(shù)據(jù)之道 (ID:PyDataLab)

作者：陽哥

大家好，我是陽哥。

最近一段時間，我在微信視頻號「Python數(shù)據(jù)之道」上陸陸續(xù)續(xù)發(fā)布了10種經(jīng)典排序算法的動畫實現(xiàn)。

今天，想以圖文以及動畫的形式，詳細的跟大家分享下。

10種經(jīng)典排序算法包括冒泡排序、選擇排序、快速排序、歸并排序、堆排序、插入排序、希爾排序、計數(shù)排序、桶排序、基數(shù)排序等。

當然，還有一些其他的排序算法，大家可以繼續(xù)去研究下。

01冒泡排序

冒泡排序（Bubble Sort）是一種比較簡單的排序算法，它重復(fù)地走訪過要排序的元素，依次比較相鄰兩個元素，如果它們的順序錯誤就把他們調(diào)換過來，直到?jīng)]有元素再需要交換，排序完成。

注：上圖中，數(shù)字表示的是數(shù)據(jù)序列原始的索引號。

算法過程

• 比較相鄰的元素，如果前一個比后一個大，就把它們兩個對調(diào)位置。

• 對排序數(shù)組中每一對相鄰元素做同樣的工作，直到全部完成，此時最后的元素將會是本輪排序中最大的數(shù)。

• 對剩下的元素繼續(xù)重復(fù)以上的步驟，直到?jīng)]有任何一個元素需要比較。

冒泡排序每次找出一個最大的元素，因此需要遍歷 n-1 次 （n為數(shù)據(jù)序列的長度）。

算法特點

什么時候最快（Best Cases）：當輸入的數(shù)據(jù)已經(jīng)是正序時。

什么時候最慢（Worst Cases）：當輸入的數(shù)據(jù)是反序時。

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

算法動畫演示

冒泡排序的動態(tài)演示如下：

02選擇排序

選擇排序原理

選擇排序（Selection Sort）的原理，每一輪從待排序的記錄中選出最小的元素，存放在序列的起始位置，然后再從剩余的未排序元素中尋找到最小元素，然后放到已排序的序列的末尾。以此類推，直到全部待排序的數(shù)據(jù)元素的個數(shù)為零。得到數(shù)值從小到達排序的數(shù)據(jù)序列。

也可以每一輪找出數(shù)值最大的元素，這樣的話，排序完畢后的數(shù)組最終是從大到小排列。

選擇排序每次選出最小（最大）的元素，因此需要遍歷 n-1 次。

Python代碼

def?selection_sort(lst):for?i?in?range(len(lst)?-?1):??min_index?=?ifor?j?in?range(i?+?1,?len(lst)):if?lst[j]?<?lst[min_index]:min_index?=?j??lst[i],?lst[min_index]?=?lst[min_index],?lst[i]?return?lst

算法動畫演示

選擇排序的動態(tài)演示如下：

03快速排序

快速排序（Quick Sort），是在上世紀60年代，由美國人東尼·霍爾提出的一種排序方法。這種排序方式，在當時已經(jīng)是非常快的一種排序了。因此在命名上，才將之稱為“快速排序”。

算法過程

先從數(shù)據(jù)序列中取出一個數(shù)作為基準數(shù)（baseline，習慣取第一個數(shù)）。

分區(qū)過程，將比基準數(shù)小的數(shù)全放到它的左邊,大于或等于它的數(shù)全放到它的右邊。

再對左右區(qū)間遞歸(recursive)重復(fù)第二步，直到各區(qū)間只有一個數(shù)。

因為數(shù)據(jù)序列之間的順序都是固定的。最后將這些子序列一次組合起來，整體的排序就完成了。

如下圖，對于數(shù)據(jù)序列，先取第一個數(shù)據(jù) 15為基準數(shù)，將比 15 小的數(shù)放在左邊，比 15 大（大于或等于）的數(shù)放在右邊

接下來，對于左邊部分，重復(fù)上面的步驟，如下圖，取左邊序列的第一個數(shù)據(jù) 11 為基準數(shù)，將比 11 小的數(shù)放在左邊，比 11 大（大于或等于）的數(shù)放在右邊。

繼續(xù)遞歸重復(fù)上述過程，直到每個區(qū)間只有一個數(shù)。這樣就會完成排序

Python代碼

def?quick_sort(lst):??n?=?len(lst)if?n?<=?1:return?lstbaseline?=?lst[0]?left?=?[lst[i]?for?i?in?range(1,?len(lst))?if?lst[i]?<?baseline]?right?=?[lst[i]?for?i?in?range(1,?len(lst))?if?lst[i]?>=?baseline]return?quick_sort(left)?+?[baseline]?+?quick_sort(right)

算法動畫演示

快速排序的動態(tài)演示如下：

04歸并排序

算法思想

歸并排序（Merge Sort）是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法的一個非常典型的應(yīng)用，歸并排序?qū)蓚€已經(jīng)有序的子序列合并成一個有序的序列。

算法流程

主要兩步(拆分，合并)

• 步驟１：進行序列拆分，一直拆分到只有一個元素；

• 步驟２：拆分完成后，開始遞歸合并。

思路：假設(shè)我們有一個沒有排好序的序列，那么我們首先使用拆分的方法將這個序列分割成一個個已經(jīng)排好序的子序列（直到剩下一個元素）。然后再利用歸并方法將一個個有序的子序列合并成排好序的序列。

圖解算法

拆分

對于數(shù)據(jù)序列 [15,11,13,18,10] ,我們從首先從數(shù)據(jù)序列的中間位置開始拆分，中間位置的設(shè)置為

首次拆分如下：

第一次拆分后，依次對子序列進行拆分，拆分過程如下：

合并

合并過程中，對于左右分區(qū)以及其子區(qū)間，遞歸使用合并方法。先從左邊最小的子區(qū)間開始，對于每個區(qū)間，依次將最小的數(shù)據(jù)放在最左邊，然后對右邊區(qū)間也執(zhí)行同樣的操作。

合并過程的完整圖示如下：

Python代碼

def?merge_sort(lst):def?merge(left,right):i?=?0j?=?0???result?=?[]????while?i?<?len(left)?and?j?<?len(right):??if?left[i]?<=?right[j]:????result.append(left[i])i?+=?1else:result.append(right[j])j?+=?1result?=?result?+?left[i:]?+?right[j:]return?resultn?=?len(lst)if?n?<=?1:?????return?lst?mid?=?n?//?2?left?=?merge_sort(lst[:mid])right?=?merge_sort(lst[mid:])return?merge(left,right)

算法動畫演示

歸并排序的動態(tài)演示如下：

05堆排序

要理解堆排序（Heap Sort）算法，首先要知道什么是“堆”。

堆的定義

對于 n 個元素的數(shù)據(jù)序列 ，當且僅當滿足下列情形之一時，才稱之為 堆:

情形1：

情形2：

若序列 是堆，則堆頂元素必為序列中n個元素的最小值或最大值。

小頂堆如下圖所示：

小頂堆

大頂堆如下圖所示：

大頂堆

若在輸出堆頂?shù)淖钚≈?#xff08;或最大值）之后，使得剩余n-1個元素的序列重又建成一個堆，則得到n個元素的次小值（或次大值）。如此反復(fù)執(zhí)行，便能得到一個有序序列，這個過程稱之為 堆排序。

堆的存儲

一般用數(shù)組來表示堆，若根結(jié)點存在序號 0 處， i 結(jié)點的父結(jié)點下標就為 (i-1)/2。i 結(jié)點的左右子結(jié)點下標分別為 2*i+1和 2*i+2 。

對于上面提到的小頂堆和大頂堆，其數(shù)據(jù)存儲情況如下：

小頂堆大頂堆

每幅圖的右邊為其數(shù)據(jù)存儲結(jié)構(gòu)，左邊為其邏輯結(jié)構(gòu)。

堆排序

實現(xiàn)堆排序需要解決兩個問題：

如何由一個無序序列建成一個堆？

如何在輸出堆頂元素之后，調(diào)整剩余元素成為一個新的堆？

堆的初始化

第一個問題實際上就是堆的初始化，下面來闡述下如何構(gòu)造初始堆，假設(shè)初始的數(shù)據(jù)序列如下：

咱們首先需要將其以樹形結(jié)構(gòu)來展示，如下：

初始化堆的時候是對所有的非葉子結(jié)點進行篩選。

最后一個非終端元素的下標是 [n/2] 向下取整，所以篩選只需要從第 [n/2] 向下取整個元素開始，從后往前進行調(diào)整。

從最后一個非葉子結(jié)點開始，每次都是從父結(jié)點、左邊子節(jié)點、右邊子節(jié)點中進行比較交換，交換可能會引起子結(jié)點不滿足堆的性質(zhì)，所以每次交換之后需要重新對被交換的子結(jié)點進行調(diào)整。

以小頂堆為例，構(gòu)造初始堆的過程如下：

進行堆排序

有了初始堆之后就可以進行排序了。

堆排序是一種選擇排序。建立的初始堆為初始的無序區(qū)。

排序開始，首先輸出堆頂元素（因為它是最值），將堆頂元素和最后一個元素交換，這樣，第n個位置（即最后一個位置）作為有序區(qū)，前n-1個位置仍是無序區(qū)，對無序區(qū)進行調(diào)整，得到堆之后，再交換堆頂和最后一個元素，這樣有序區(qū)長度變?yōu)?。。。

大頂堆交換堆頂元素和最后的元素無序區(qū)-1，有序區(qū)+1

不斷進行此操作，將剩下的元素重新調(diào)整為堆，然后輸出堆頂元素到有序區(qū)。每次交換都導(dǎo)致無序區(qū)-1，有序區(qū)+1。不斷重復(fù)此過程直到有序區(qū)長度增長為n-1，排序完成。

對于堆初始化，以及堆排序，最好還是通過視頻演示來理解，這樣更直觀。

堆排序的動態(tài)演示如下：

Python代碼

def?heap_sort(lst):def?adjust_heap(lst,?i,?size):left_index?=?2?*?i?+?1right_index?=?2?*?i?+?2largest_index?=?i?if?left_index?<?size?and?lst[left_index]?>?lst[largest_index]:?largest_index?=?left_index?if?right_index?<?size?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)就是每一步都將一個需要排序的數(shù)據(jù)按其大小插入到已經(jīng)排序的數(shù)據(jù)序列中的適當位置，直到全部插入完畢。

插入排序如同打撲克牌一樣，每次將后面的牌插到前面已經(jīng)排好序的牌中。

Python代碼

def?insertion_sort(lst):for?i?in?range(len(lst)?-?1):cur_num,?pre_index?=?lst[i+1],?iwhile?pre_index?>=?0?and?cur_num?<?lst[pre_index]:lst[pre_index?+?1]?=?lst[pre_index]pre_index?-=?1lst[pre_index?+?1]?=?cur_num?return?lst

算法動畫演示

插入排序的動態(tài)演示如下：

07希爾排序

基本原理

希爾排序(Shell Sort)是插入排序的一種更高效率的實現(xiàn)。

希爾排序的核心在于間隔序列的設(shè)定。既可以提前設(shè)定好間隔序列，也可以動態(tài)的定義間隔序列。

這里以動態(tài)間隔序列為例來描述。初始間隔（gap值）為數(shù)據(jù)序列長度除以2取整，后續(xù)間隔以 前一個間隔數(shù)值除以2取整為循環(huán)，直到最后一個間隔值為 1 。

對于下面這個數(shù)據(jù)序列，初始間隔數(shù)值為5

先將數(shù)據(jù)序列按間隔進行子序列分組，第一個子序列的索引為[0,5,10]，這里分成了5組。

為方便大家區(qū)分不同的子序列，對同一個子序列標注相同的顏色，分組情況如下：

分組結(jié)束后，子序列內(nèi)部進行插入排序，gap為5的子序列內(nèi)部排序后如下：

注：紅色箭頭標注的地方，是子序列內(nèi)部排序后的狀態(tài)

接下來選取第二個間隔值，按照間隔值進行子序列分組，同樣地，子序列內(nèi)部分別進行插入排序；

如果數(shù)據(jù)序列比較長，則會選取第3個、第4個或者更多個間隔值，重復(fù)上述的步驟。

gap為2的排序情況前后對照如下：

最后一個間隔值為1，這一次相當于簡單的插入排序。但是經(jīng)過前幾次排序，序列已經(jīng)基本有序，因此最后一次排序時間效率就提高了很多。

Python代碼

def?shell_sort(lst):n?=?len(lst)gap?=?n?//?2while?gap?>?0:for?i?in?range(gap,?n):for?j?in?range(i,?gap?-?1,?-gap):if?lst[j]?<?lst[j?-?gap]:lst[j],?lst[j?-?gap]?=?lst[j?-?gap],?lst[j]else:breakgap?//=?2return?lst

算法動畫演示

希爾排序的動態(tài)演示如下：

08計數(shù)排序

基本原理

計數(shù)排序（Counting Sort）的核心在于將輸入的數(shù)據(jù)值轉(zhuǎn)化為鍵，存儲在額外開辟的數(shù)組空間中。計數(shù)排序要求輸入的數(shù)據(jù)必須是有確定范圍的整數(shù)。

算法的步驟如下：

先找出待排序的數(shù)組中最大和最小的元素，新開辟一個長度為 最大值-最小值+1 的數(shù)組；

然后，統(tǒng)計原數(shù)組中每個元素出現(xiàn)的次數(shù)，存入到新開辟的數(shù)組中；

接下來，根據(jù)每個元素出現(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]?+=?1i?=?0for?j?in?range(len(bucket)):while?bucket[j]?>?0:lst[i]?=?j?+?nums_minbucket[j]?-=?1i?+=?1return?lst

算法動畫演示

計數(shù)排序的動態(tài)演示如下：

09桶排序

基本思想

簡單來說，桶排序（Bucket Sort）就是把數(shù)據(jù)分組，放在一個個的桶中，對每個桶里面的數(shù)據(jù)進行排序，然后將桶進行數(shù)據(jù)合并，完成桶排序。

該算法分為四步，包括劃分桶、數(shù)據(jù)入桶、桶內(nèi)排序、數(shù)據(jù)合并。

桶的劃分過程

這里詳細介紹下桶的劃分過程。

對于一個數(shù)值范圍在10到 49范圍內(nèi)的數(shù)組，我們?nèi)⊥暗拇笮?0 （defaultBucketSize = 10），則第一個桶的范圍為 10到20，第二個桶的數(shù)據(jù)范圍是20到30，依次類推。最后，我們一共需要4個桶來放入數(shù)據(jù)。

排序過程

對于下面這個數(shù)據(jù)序列，初始設(shè)定桶的大小為 20 （defaultBucketSize = 20），經(jīng)計算，一共需要4個桶來放入數(shù)據(jù)。

然后將原始數(shù)組按數(shù)值大小放入到對應(yīng)的桶中，完成數(shù)據(jù)分組。

對于桶內(nèi)的數(shù)據(jù)序列，這時可以用冒泡排序、選擇排序等多種排序算法來對數(shù)據(jù)進行排序。這些算法，在之前的視頻里已有介紹，大家可以去了解下。

這里，我選用 冒泡排序 來對桶內(nèi)數(shù)據(jù)進行排序。

桶內(nèi)排序完成后，將數(shù)據(jù)按桶的順序進行合并，這樣就得到所有數(shù)值排好序的數(shù)據(jù)序列了

詳細的動畫演示過程如下：

Python代碼

def?bucket_sort(lst,?defaultBucketSize=4):maxVal,?minVal?=?max(lst),?min(lst)bucketSize?=?defaultBucketSizebucketCount?=?(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），它是透過鍵值的部份信息，將要排序的元素分配至某些“桶”中，以達到排序的作用。

基數(shù)排序適用于所有元素均為正整數(shù)的數(shù)組。

基本思想

排序過程分為“分配”和“收集”。

排序過程中，將元素分層為多個關(guān)鍵碼進行排序（一般按照數(shù)值的個位、十位、百位、…… 進行區(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的效率會比較好，MSD的方式恰與LSD相反，是由高位數(shù)為基底開始進行分配，其他的演算方式則都相同。

算法流程

這里以最低位優(yōu)先LSD為例。

先根據(jù)個位數(shù)的數(shù)值，在掃描數(shù)值時將它們分配至編號0到9的桶中，然后將桶子中的數(shù)值串接起來。

將這些桶子中的數(shù)值重新串接起來，成為新的序列，接著再進行一次分配，這次是根據(jù)十位數(shù)來分配。

如果排序的對象有三位數(shù)以上，則持續(xù)進行以上的動作直至最高位數(shù)為止。

詳細的動畫演示過程如下：

Python代碼

#?LSD?Radix?Sort def?radix_sort(lst):mod?=?10div?=?1mostBit?=?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?+=?1div?*=?10mostBit?-=?1return?lst

11小結(jié)

以上就是用 Python 來實現(xiàn)10種經(jīng)典排序算法的相關(guān)內(nèi)容。

對于這些排序算法的實現(xiàn)，代碼其實并不是最主要的，重要的是需要去理解各種算法的基本思想、基本原理以及其內(nèi)部的實現(xiàn)過程。

對于每種算法，用其他編程語言同樣是可以去實現(xiàn)的。

并且，對于同一種算法，即使只用 Python 語言，也有多種不同的代碼方式可以來實現(xiàn)，但其基本原理是一致的。

對于本篇文章分享的內(nèi)容，對于我自己而言，最難的還是以動畫的形式，將這些算法的原理實現(xiàn)出來。

如果大家覺得這種形式不錯，我也會考慮以這種形式分享一些其他相關(guān)的內(nèi)容。

BTW，在微信視頻號「Python數(shù)據(jù)之道」發(fā)布這些算法動畫視頻的過程中，不少同學(xué)都在問我這些視頻是怎么做的，用什么工具做的，…… ，諸如此類的問題。

如果本篇文章 “在看” 數(shù)量超過 100 個的話，我會考慮來介紹這些動畫視頻是怎么做的哈。

---

參考文檔

• 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

---

大家讀完順手點下右下角的 ?“在看” ，就是最大的鼓勵和支持了。

往期精彩回顧適合初學(xué)者入門人工智能的路線及資料下載機器學(xué)習及深度學(xué)習筆記等資料打印機器學(xué)習在線手冊深度學(xué)習筆記專輯《統(tǒng)計學(xué)習方法》的代碼復(fù)現(xiàn)專輯 AI基礎(chǔ)下載黃海廣老師《機器學(xué)習課程》視頻課黃海廣老師《機器學(xué)習課程》711頁完整版課件

本站qq群955171419，加入微信群請掃碼：

總結(jié)

以上是生活随笔為你收集整理的【Python】用Python实现十大经典排序算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。