點(diǎn)擊上方“小白學(xué)視覺”，選擇加"星標(biāo)"或“置頂”

重磅干貨，第一時(shí)間送達(dá)

今天將為大家介紹常用的十大排序算法中最簡(jiǎn)單的五種（冒泡、選擇、插入、希爾、歸并），主要從：過程圖解、算法思想、代碼實(shí)現(xiàn)、算法分析這四個(gè)方面講解，建議大家看完之后自己動(dòng)手練習(xí)加強(qiáng)記憶！

注：本文使用的復(fù)雜度均為最壞復(fù)雜度

冒泡排序（Bubble Sort），是一種計(jì)算機(jī)科學(xué)領(lǐng)域的較簡(jiǎn)單的排序算法。它重復(fù)地走訪過要排序的元素列，依次比較兩個(gè)相鄰的元素，一層一層的將較大的元素往后移動(dòng)，其現(xiàn)象和氣泡在上升過程中慢慢變大類似，故成為冒泡排序。

1.過程圖解

2.算法思想

1. 從第一個(gè)和第二個(gè)開始比較，如果第一個(gè)比第二個(gè)大，則交換位置，然后比較第二個(gè)和第三個(gè)，逐漸往后

2. 經(jīng)過第一輪后最大的元素已經(jīng)排在最后，所以重復(fù)上述操作的話第二大的則會(huì)排在倒數(shù)第二的位置。

3. 那重復(fù)上述操作n-1次即可完成排序，因?yàn)樽詈笠淮沃挥幸粋€(gè)元素所以不需要比較

3.代碼實(shí)現(xiàn)

def bubble_sort(arr):"""冒泡排序"""# 第一層for表示循環(huán)的遍數(shù)for i in range(len(arr) - 1):# 第二層for表示具體比較哪兩個(gè)元素for j in range(len(arr) - 1 - i):if arr[j] > arr[j + 1]:# 如果前面的大于后面的，則交換這兩個(gè)元素的位置                arr[j], arr[j + 1] = arr[j + 1], arr[j]return arr

4.算法分析

冒泡排序是一種簡(jiǎn)單直接暴力的排序算法，為什么說它暴力？因?yàn)槊恳惠啽容^可能多個(gè)元素移動(dòng)位置，而元素位置的互換是需要消耗資源的，所以這是一種偏慢的排序算法，僅適用于對(duì)于含有較少元素的數(shù)列進(jìn)行排序。

1. 穩(wěn)定性：我們從代碼中可以看出只有前一個(gè)元素大于后一個(gè)元素才可能交換位置，所以相同元素的相對(duì)順序不可能改變，所以它是穩(wěn)定排序

2. 比較性：因?yàn)榕判驎r(shí)元素之間需要比較，所以是比較排序

3. 時(shí)間復(fù)雜度：因?yàn)樗枰p層循環(huán)n*(n-1))，所以平均時(shí)間復(fù)雜度為O(n^2)

4. 空間復(fù)雜度：只需要常數(shù)個(gè)輔助單元，所以空間復(fù)雜度為O(1)，我們把空間復(fù)雜度為O(1)的排序成為原地排序（in-place）

5. 記憶方法：想象成氣泡，一層一層的往上變大

選擇排序（Selection sort）是一種簡(jiǎn)單直觀的排序算法。它的工作原理是每一次從待排序的數(shù)據(jù)元素中選出最小（或最大）的一個(gè)元素，存放在序列的起始位置，所以稱為：選擇排序

1.過程圖解

2.算法思想

1. 設(shè)第一個(gè)元素為比較元素，依次和后面的元素比較，比較完所有元素找到最小的元素，將它和第一個(gè)元素互換

2. 重復(fù)上述操作，我們找出第二小的元素和第二個(gè)位置的元素互換，以此類推找出剩余最小元素將它換到前面，即完成排序

3.代碼實(shí)現(xiàn)

def selection_sort(arr):"""選擇排序"""# 第一層for表示循環(huán)選擇的遍數(shù)for i in range(len(arr) - 1):# 將起始元素設(shè)為最小元素        min_index = i# 第二層for表示最小元素和后面的元素逐個(gè)比較for j in range(i + 1, len(arr)):if arr[j] < arr[min_index]:# 如果當(dāng)前元素比最小元素小，則把當(dāng)前元素角標(biāo)記為最小元素角標(biāo)                min_index = j# 查找一遍后將最小元素與起始元素互換        arr[min_index], arr[i] = arr[i], arr[min_index]return arr

4.算法分析

選擇排序和冒泡排序很類似，但是選擇排序每輪比較只會(huì)有一次交換，而冒泡排序會(huì)有多次交換，交換次數(shù)比冒泡排序少，就減少cpu的消耗，所以在數(shù)據(jù)量小的時(shí)候可以用選擇排序，實(shí)際適用的場(chǎng)合非常少。

1. 比較性：因?yàn)榕判驎r(shí)元素之間需要比較，所以是比較排序

2. 穩(wěn)定性：因?yàn)榇嬖谌我馕恢玫膬蓚€(gè)元素交換，比如[5, ?8, 5, 2]，第一個(gè)5會(huì)和2交換位置，所以改變了兩個(gè)5原來的相對(duì)順序，所以為不穩(wěn)定排序。

3. 時(shí)間復(fù)雜度：我們看到選擇排序同樣是雙層循環(huán)n*(n-1))，所以時(shí)間復(fù)雜度也為：O(n^2)

4. 空間復(fù)雜度：只需要常數(shù)個(gè)輔助單元，所以空間復(fù)雜度也為O(1)

5. 記憶方法：選擇對(duì)象要先選最小的，因?yàn)槟?，哈?/span>

插入排序（Insertion-Sort）的算法描述是一種簡(jiǎn)單直觀的排序算法。它的工作原理是通過構(gòu)建有序序列，對(duì)于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。

1.過程圖解

2.算法思想

1. 從第二個(gè)元素開始和前面的元素進(jìn)行比較，如果前面的元素比當(dāng)前元素大，則將前面元素 后移，當(dāng)前元素依次往前，直到找到比它小或等于它的元素插入在其后面

2. 然后選擇第三個(gè)元素，重復(fù)上述操作，進(jìn)行插入

3. 依次選擇到最后一個(gè)元素，插入后即完成所有排序

3.代碼實(shí)現(xiàn)

def insertion_sort(arr):"""插入排序"""# 第一層for表示循環(huán)插入的遍數(shù)for i in range(1, len(arr)):# 設(shè)置當(dāng)前需要插入的元素        current = arr[i]# 與當(dāng)前元素比較的比較元素        pre_index = i - 1while pre_index >= 0 and arr[pre_index] > current:# 當(dāng)比較元素大于當(dāng)前元素則把比較元素后移            arr[pre_index + 1] = arr[pre_index]# 往前選擇下一個(gè)比較元素            pre_index -= 1# 當(dāng)比較元素小于當(dāng)前元素，則將當(dāng)前元素插入在 其后面        arr[pre_index + 1] = currentreturn arr

4.算法分析

插入排序的適用場(chǎng)景：一個(gè)新元素需要插入到一組已經(jīng)是有序的數(shù)組中，或者是一組基本有序的數(shù)組排序。

1. 比較性：排序時(shí)元素之間需要比較，所以為比較排序

2. 穩(wěn)定性：從代碼我們可以看出只有比較元素大于當(dāng)前元素，比較元素才會(huì)往后移動(dòng)，所以相同元素是不會(huì)改變相對(duì)順序

3. 時(shí)間復(fù)雜度：插入排序同樣需要兩次循壞一個(gè)一個(gè)比較，故時(shí)間復(fù)雜度也為O(n^2)

4. 空間復(fù)雜度：只需要常數(shù)個(gè)輔助單元，所以空間復(fù)雜度也為O(1)

5. 記憶方法：想象成在書架中插書：先找到相應(yīng)位置，將后面的書往后推，再將書插入

希爾排序(Shell’s Sort)是插入排序的一種又稱“縮小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一種更高效的改進(jìn)版本，它與插入排序的不同之處在于，它會(huì)優(yōu)先比較距離較遠(yuǎn)的元素，該方法因D.L.Shell于1959年提出而得名。

1.過程圖解

2.算法思想

希爾排序的整體思想是將固定間隔的幾個(gè)元素之間排序，然后再縮小這個(gè)間隔。這樣到最后數(shù)列就成為了基本有序數(shù)列，而前面我們講過插入排序對(duì)基本有序數(shù)列排序效果較好。

1. 計(jì)算一個(gè)增量（間隔）值

2. 對(duì)元素進(jìn)行增量元素進(jìn)行比較，比如增量值為7，那么就對(duì)0,7,14,21…個(gè)元素進(jìn)行插入排序

3. 然后對(duì)1,8,15…進(jìn)行排序，依次遞增進(jìn)行排序

4. 所有元素排序完后，縮小增量比如為3，然后又重復(fù)上述第2，3步

5. 最后縮小增量至1時(shí)，數(shù)列已經(jīng)基本有序，最后一遍普通插入即可

已知的最增量式是由 Sedgewick 提出的 (1, 5, 19, 41, 109,…)，該步長(zhǎng)的項(xiàng)來自 9 4^i - 9 2^i + 1 和 4^i - 3 2^i + 1 這兩個(gè)算式。這項(xiàng)研究也表明 “比較在希爾排序中是最主要的操作，而不是交換。用這樣增量式的希爾排序比插入排序和堆排序都要快，甚至在小數(shù)組中比快速排序還快，但是在涉及大量數(shù)據(jù)時(shí)希爾排序還是比*快速排序慢。

3.代碼實(shí)現(xiàn)

def shell_sort(arr):"""希爾排序"""# 取整計(jì)算增量（間隔）值    gap = len(arr) // 2while gap > 0:# 從增量值開始遍歷比較for i in range(gap, len(arr)):            j = i            current = arr[i]# 元素與他同列的前面的每個(gè)元素比較，如果比前面的小則互換while j - gap >= 0 and current < arr[j - gap]:                arr[j] = arr[j - gap]                j -= gap            arr[j] = current# 縮小增量（間隔）值        gap //= 2return arr

4.算法分析

1. 比較性：排序時(shí)元素之間需要比較，所以為比較排序

2. 穩(wěn)定性：因?yàn)橄柵判蚴情g隔的插入，所以存在相同元素相對(duì)順序被打亂，所以是不穩(wěn)定排序

3. 時(shí)間復(fù)雜度：? ?最壞時(shí)間復(fù)雜度O(n^2)平均復(fù)雜度為O(n^1.3)

4. 空間復(fù)雜度：只需要常數(shù)個(gè)輔助單元，所以空間復(fù)雜度也為O(1)

5. 記憶方法：插入排序是每輪都是一小步，希爾排序是先大步后小步，它第一個(gè)突破O(n2)的排序算法。聯(lián)想起阿姆斯特朗登月之后說：這是我個(gè)人一小步，卻是人類邁出的一大步。

歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。歸并排序適用于子序列有序的數(shù)據(jù)排序。

1.過程圖解

2.算法思想

歸并排序是分治法的典型應(yīng)用。分治法（Divide-and-Conquer）：將原問題劃分成 n 個(gè)規(guī)模較小而結(jié)構(gòu)與原問題相似的子問題；遞歸地解決這些問題，然后再合并其結(jié)果，就得到原問題的解。從上圖看分解后的數(shù)列很像一個(gè)二叉樹。

1. 使用遞歸將源數(shù)列使用二分法分成多個(gè)子列

2. 申請(qǐng)空間將兩個(gè)子列排序合并然后返回

3. 將所有子列一步一步合并最后完成排序

3.代碼實(shí)現(xiàn)

def merge_sort(arr):"""歸并排序"""if len(arr) == 1:return arr# 使用二分法將數(shù)列分兩個(gè)    mid = len(arr) // 2    left = arr[:mid]    right = arr[mid:]# 使用遞歸運(yùn)算return marge(merge_sort(left), merge_sort(right))

def marge(left, right):"""排序合并兩個(gè)數(shù)列"""    result = []# 兩個(gè)數(shù)列都有值while len(left) > 0 and len(right) > 0:# 左右兩個(gè)數(shù)列第一個(gè)最小放前面if left[0] <= right[0]:            result.append(left.pop(0))else:            result.append(right.pop(0))# 只有一個(gè)數(shù)列中還有值，直接添加    result += left    result += rightreturn result

4.算法分析

1. 比較性：排序時(shí)元素之間需要比較，所以為比較排序

2. 穩(wěn)定性：我們從代碼中可以看到當(dāng)左邊的元素小于等于右邊的元素就把左邊的排前面，而原本左邊的就是在前面，所以相同元素的相對(duì)順序不變，故為穩(wěn)定排序

3. 時(shí)間復(fù)雜度：? ?復(fù)雜度為O(nlog^n)

4. 空間復(fù)雜度：在合并子列時(shí)需要申請(qǐng)臨時(shí)空間，而且空間大小隨數(shù)列的大小而變化，所以空間復(fù)雜度為O(n)

5. 記憶方法：所謂歸并肯定是要先分解，再合并

今天給大家介紹的五種排序是比較簡(jiǎn)單的排序，建議大家自己動(dòng)手敲幾遍代碼，書讀百遍，其義自現(xiàn)。要求大家必須理解&記住它們的算法原理，因?yàn)榇a是永遠(yuǎn)記不住的，只要記住原理你就能用偽代碼實(shí)現(xiàn)。為了方便大家記憶我在每個(gè)算法分析最后給出了自己的記憶方法，如果你有更合適的記憶方法，歡迎在下方留言，同時(shí)也歡迎大家轉(zhuǎn)發(fā)分享！

交流群

歡迎加入公眾號(hào)讀者群一起和同行交流，目前有SLAM、三維視覺、傳感器、自動(dòng)駕駛、計(jì)算攝影、檢測(cè)、分割、識(shí)別、醫(yī)學(xué)影像、GAN、算法競(jìng)賽等微信群（以后會(huì)逐漸細(xì)分），請(qǐng)掃描下面微信號(hào)加群，備注：”昵稱+學(xué)校/公司+研究方向“，例如：”張三?+?上海交大?+?視覺SLAM“。請(qǐng)按照格式備注，否則不予通過。添加成功后會(huì)根據(jù)研究方向邀請(qǐng)進(jìn)入相關(guān)微信群。請(qǐng)勿在群內(nèi)發(fā)送廣告，否則會(huì)請(qǐng)出群，謝謝理解~