今天晶疼，詳細(xì)的跟大家分享下 10 種經(jīng)典排序算法酒贬。

10種經(jīng)典排序算法包括冒泡排序、選擇排序翠霍、快速排序锭吨、歸并排序、堆排序寒匙、插入排序零如、希爾排序、計數(shù)排序锄弱、桶排序考蕾、基數(shù)排序等。

當(dāng)然会宪，還有一些其他的排序算法肖卧，大家可以繼續(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ù)序列的長度）。

算法特點(diǎn)

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

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

Python代碼

def bubble_sort(lst):

n?=?len(lst)

foriinrange(n):

forjinrange(1,?n?-?i):

iflst[j?-1]?>?lst[j]:

lst[j?-1],?lst[j]?=?lst[j],?lst[j?-1]

returnlst

02選擇排序

選擇排序原理

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

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

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

Python代碼

defselection_sort(lst):

foriinrange(len(lst)?-1):

min_index?=?i

forjinrange(i?+1,?len(lst)):

iflst[j]?<?lst[min_index]:

min_index?=?j

lst[i],?lst[min_index]?=?lst[min_index],?lst[i]

returnlst

03快速排序

快速排序（Quick Sort），是在上世紀(jì)60年代庶近，由美國人東尼·霍爾提出的一種排序方法鸭巴。這種排序方式，在當(dāng)時已經(jīng)是非忱鬼铮快的一種排序了。因此在命名上溪椎，才將之稱為“快速排序”普舆。

算法過程

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

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

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

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

如下圖钞螟，對于數(shù)據(jù)序列，先取第一個數(shù)據(jù)?15為基準(zhǔn)數(shù)谎碍，將比?15?小的數(shù)放在左邊鳞滨，比?15?大（大于或等于）的數(shù)放在右邊

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

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

Python代碼

def quick_sort(lst):

n?=?len(lst)

ifn?<=1:

return lst

baseline?=?lst[0]

left?=?[lst[i]foriinrange(1,?len(lst))iflst[i]?<?baseline]

right?=?[lst[i]foriinrange(1,?len(lst))iflst[i]?>=?baseline]

returnquick_sort(left)?+?[baseline]?+?quick_sort(right)

算法思想

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

算法流程

主要兩步(拆分，合并)

步驟１：進(jìn)行序列拆分趁餐，一直拆分到只有一個元素喷兼；

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

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

圖解算法

拆分

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

首次拆分如下：

第一次拆分后，依次對子序列進(jìn)行拆分候学，拆分過程如下：

合并

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

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

Python代碼

defmerge_sort(lst):

defmerge(left,right):

i?=0

j?=0

result?=?[]

whilei?<?len(left)andj?<?len(right):

ifleft[i]?<=?right[j]:

result.append(left[i])

i?+=1

else:

result.append(right[j])

j?+=1

result?=?result?+?left[i:]?+?right[j:]

returnresult

n?=?len(lst)

ifn?<=1:

returnlst

mid?=?n?//2

left?=?merge_sort(lst[:mid])

right?=?merge_sort(lst[mid:])

returnmerge(left,right)

05 堆排序

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

堆的定義

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

情形1：

情形2：

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

小頂堆如下圖所示：

小頂堆

大頂堆如下圖所示：

大頂堆

若在輸出堆頂?shù)淖钚≈担ɑ蜃畲笾担┲笙睾茫沟檬Ｓ鄋-1個元素的序列重又建成一個堆，則得到n個元素的次小值（或次大值）趣倾。如此反復(fù)執(zhí)行聘惦，便能得到一個有序序列，這個過程稱之為?堆排序儒恋。

堆的存儲

一般用數(shù)組來表示堆善绎，若根結(jié)點(diǎn)存在序號?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?禀酱。

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

小頂堆

大頂堆

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

堆排序

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

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

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

堆的初始化

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

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

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

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

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

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

進(jìn)行堆排序

有了初始堆之后就可以進(jìn)行排序了到推。

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

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

大頂堆

交換堆頂元素和最后的元素

無序區(qū)-1哥捕，有序區(qū)+1

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

Python代碼

defheap_sort(lst):

defadjust_heap(lst,?i,?size):

left_index?=2*?i?+1

right_index?=2*?i?+2

largest_index?=?i

ifleft_index?<?sizeandlst[left_index]?>?lst[largest_index]:

largest_index?=?left_index

ifright_index?<?sizeandlst[right_index]?>?lst[largest_index]:

largest_index?=?right_index

iflargest_index?!=?i:

lst[largest_index],?lst[i]?=?lst[i],?lst[largest_index]

adjust_heap(lst,?largest_index,?size)

defbuilt_heap(lst,?size):

foriinrange(len(lst)//2)[::-1]:

adjust_heap(lst,?i,?size)

size?=?len(lst)

built_heap(lst,?size)

foriinrange(len(lst))[::-1]:

lst[0],?lst[i]?=?lst[i],?lst[0]

adjust_heap(lst,0,?i)

returnlst

06 插入排序

插入排序(Insertion Sort)就是每一步都將一個需要排序的數(shù)據(jù)按其大小插入到已經(jīng)排序的數(shù)據(jù)序列中的適當(dāng)位置孕惜，直到全部插入完畢愧薛。

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

Python代碼

definsertion_sort(lst):

foriinrange(len(lst)?-1):

cur_num,?pre_index?=?lst[i+1],?i

whilepre_index?>=0andcur_num?<?lst[pre_index]:

lst[pre_index?+1]?=?lst[pre_index]

pre_index?-=1

lst[pre_index?+1]?=?cur_num

returnlst

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ù)序列按間隔進(jìn)行子序列分組四濒，第一個子序列的索引為[0,5,10]，這里分成了5組职辨。

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

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

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

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

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

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

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

Python代碼

defshell_sort(lst):

n?=?len(lst)

gap?=?n?//2

whilegap?>0:

foriinrange(gap,?n):

forjinrange(i,?gap?-1,?-gap):

iflst[j]?<?lst[j?-?gap]:

lst[j],?lst[j?-?gap]?=?lst[j?-?gap],?lst[j]

else:

break

gap?//=2

returnlst

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代碼

defcounting_sort(lst):

nums_min?=?min(lst)

bucket?=?[0]?*?(max(lst)?+1-?nums_min)

fornuminlst:

bucket[num?-?nums_min]?+=1

i?=0

forjinrange(len(bucket)):

whilebucket[j]?>0:

lst[i]?=?j?+?nums_min

bucket[j]?-=1

i?+=1

returnlst

09 桶排序

基本思想

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

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

桶的劃分過程

這里詳細(xì)介紹下桶的劃分過程沟绪。

對于一個數(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ù)進(jìn)行排序铆隘。這些算法，在之前的視頻里已有介紹南用，大家可以去了解下膀钠。

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

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

Python代碼

defbucket_sort(lst,?defaultBucketSize=4):

maxVal,?minVal?=?max(lst),?min(lst)

bucketSize?=?defaultBucketSize

bucketCount?=?(maxVal?-?minVal)?//?bucketSize?+1

buckets?=?[[]foriinrange(bucketCount)]

fornuminlst:

buckets[(num?-?minVal)?//?bucketSize].append(num)

lst.clear()

forbucketinbuckets:

bubble_sort(bucket)

lst.extend(bucket)

returnlst

10 基數(shù)排序

基數(shù)排序（radix sort）屬于“分配式排序”（distribution sort）筑公，它是透過鍵值的部份信息雳窟，將要排序的元素分配至某些“桶”中，以達(dá)到排序的作用匣屡。

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

基本思想

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

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

算法流程

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

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

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

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

Python代碼

#?LSD?Radix?Sort

defradix_sort(lst):

mod?=10

div?=1

mostBit?=?len(str(max(lst)))

buckets?=?[[]forrowinrange(mod)]

whilemostBit:

fornuminlst:

buckets[num?//?div?%?mod].append(num)

i?=0

for bucketinbuckets:

whilebucket:

lst[i]?=?bucket.pop(0)

i?+=1

div?*=10

mostBit?-=1

returnlst

11 小結(jié)

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

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

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

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