演算法從入門到「放棄」（4）- 插入排序

來自專欄 AnotherWorld

本系列文章

演算法從入門到「放棄」（1）- 什麼是演算法？

演算法從入門到「放棄」（2）- 分而治之和解決循環

排序系列

1. 演算法從入門到「放棄」（3）- 快速排序

本文提煉

插入排序演算法。

什麼是插入排序？

定義來自於維基百科，插入排序，Insertion Sort.

插入排序是一種簡單的排序演算法，它可以一次構建最終排序的數組（或列表）。它在大型列表上的效率要比如快速排序、堆排序或歸併排序之類的演算法效率低得多。然而，插入排序有以下幾個優點：

• 簡單易實現
• 對（相當）小的數據集很有效率，類似其他的二次排序演算法（什麼是二次排序演算法？比較演算法有兩大類，如先前我們介紹過的大O符號所定義的，二次和線性情況。二次演算法也就是O(n^2).）
• 在實踐中比其他簡單的二次演算法如選擇排序或冒泡排序更有效
• 自適應，對於已經基本排序了的數據集來說，是比較有效的：當輸入中的每個元素都不超過其排序位置的k 個位置時，時間複雜度是O(nk）
• 穩定的，不會改變具有相等鍵的元素的相對順序
• 只需要一個恆定的（1）額外的內存空間
• 可以在接收到的列表中對列表進行排序

當人們對撲克牌進行排序時，大多數人使用的方法與插入排序類似。簡單地說，每次我們從牌堆里抽一張牌握在手裡。第一張牌比不了大小，直接放手裡握著；第二張牌如果比第一張小，握在第一張牌左邊，要是比第一張大，放右邊；再抽第三張牌，如果比第一第二張牌都小，放最左邊，要是大小在前兩張牌大小的中間就握在中間，要是比前兩張都大，就放在最右邊；。。。。。以此類推。我們編程的時候和整理撲克牌的過程類似，有一個區別就是當我們把新的數值放在舊數值之前以後，我們要記得把後面的數據都往後移一個存儲單元。

基本思想

輸入：一系列的無序數字，輸入數組{a1, a2, a3 ..... an}，總共n個

經過：遍曆數組中的每一項；每次從輸入數組中提取一個數，按照它的大小插入到已經按照大小排序好的目標數組中（如果是第一個數，目標數組則為0，直接放入即可）；依次重複，直到遍歷完成。

輸出：一系列排序好的數字，目標數組{a1, a2, a3 .... an}，順序可以是a1<a2<a3<......<an.

圖解

評價演算法好壞

分類：排序演算法

目標數據結構：數組

最壞時間複雜度：比較，交換各需要 O(n^2) ；整體為O(n^2)；#最壞情況即反序，需要移動n*(n-1)/2個元素

最優時間複雜度：比較需要O(n)，交換需要O(1)；整體為O(n)；#最優情況即正序，不需要移動元素

平均時間複雜度：比較，交換各需要 O(n^2)；整體為O(n^2)

最壞空間複雜度：總共為 O(n)，輔助空間為 O(1) ，最理想，穩定

實例分析

假設現在有輸入數組 A{6 5 3 1 8 7 2 4}

1. 我們取第一個數6 放入目標數組中，目標數組現在為空，所以就放在「第一個位置」；目標數組為 A{6}

2. 取第二個數5，比第一個數小，所以放在6 前面；目標數組為 A{5, 6}

3. 取第三個數3，依次對比目標數組裡的6, 5，比它們都小，所以放在5 前面；目標數組為 A{3, 5, 6}

4. 取第四個數1，依次對比目標數組裡的6, 5, 3，比它們都小，所以放在3 前面；目標數組為 A{1, 3, 5, 6}

5. 取第五個數8，對比目標數組裡最右邊的數6，比它大，所以放在6 後面；目標數組為 A{1, 3, 5, 6, 8}

6. 取第六個數7，對比目標數組裡最右邊的數8，比它小；再對比8 前面的數字6，比它大，所以放在6 和 8之間；目標數組為 A{1, 3, 5, 6, 7, 8}

7. 取第七個數2，依次對比目標數組裡的8, 7, 6, 5, 3，比它們都小；再對比1，比它大，所以放在1 和 3之間；目標數組為 A{1, 2, 3, 5, 6, 7, 8}

8. 取第八個數4，依次對比目標數組裡的8, 7, 6, 5，比它們都小；再對比3，比它大，所以放在3 和 5之間；目標數組為 A{1, 2, 3, 4, 5, 6, 7, 8}

最終的目標數組 A{1, 2, 3, 4, 5, 6, 7, 8}

流程展示圖（圖片來源）

代碼展示

偽代碼

// 插入排除（輸入數組為A）// 第一個數字直接放入即可，不用排序for j = 2 to A.length key = A[j] // 插入A[j] 到已排序好的數組 A[1...j-1]中 i = j - 1 while i > 0 and A[i] > key A[i+1} = A[i] i = i - 1 A[i+1} = key

在下一篇文章中，將著重講的是計數排序演算法。

如果你覺得我的文章有用，順手點個贊，關注下我的專欄或則留下你的評論吧！