Contents
  1. 1. 概念
  2. 2. 時間複雜度
  3. 3. 空間複雜度
  4. 4. 穩定性
  5. 5. Code

概念

把要排序的陣列分成”尚未排序的部分”及”排序好的部分”,將未排序的數一一插入排序好的陣列,插入時會掃描已排序好的陣列,選擇適當的位置插入。實作上,”已排序好的部分”可以用一個新的陣列 or list去存,也可以寫成不另外存放,而是在原陣列完成(In-place version)。

這邊以In-place version來做例子,為了方便說明,我把要被排序的陣列(以arr簡稱)會被拆成三部分來講:

    1. 要被插入的值 : 以insertValue簡稱
    2. insertValue的左半邊 : 已經排序好的部分
    3. insertValue的右半邊 : 未排序好的部分

而arr在演算法一剛開始的狀態,就被分成這三部分,如下圖:

insertValue從arr位置1的值開始(第0個因為只有一個元素,代表已排序好)一一被插入已經排序好的部分,
插入的過程中,會由後向前一一掃描左半邊排序好的部分,看insertValue要被插入哪個位置,
而掃瞄過程中,需要反覆把”比insertValue大”的元素逐步向後挪位,為insertValue提供插入空間(如以下動畫)。
插入之後,再從右半邊未排序的部分拿出值當作insertValue繼續插入左半邊排序好的部分,重複此步驟直到最後完成排序。


(File from Insertion sort wiki, CC BY-SA 3.0)

時間複雜度

Best : O(n)
Average : O(n2)
Worst : O(n2)

空間複雜度

O(1)

穩定性

穩定

Code

See my code on github.

參考資料:
Insertion sort wiki
Sorting algorithm wiki