Insertion Sort Algorithm 插入排序法
2022-10-23 22:56:06
# Insertion Sort 插入排序法
+ 是 **O(n^2)** 的排序演算法。
+ 不斷做 insertion 的動作(插入)，可理解為每次要插入的值，都從已排列好的陣列最右方的值開始比較，找到它適合的位置。
+ 當問題的資料量較小時，使用 Insertion Sort 會很有效率，這是因為和 Quick Sort、Merge Sort、Heap Sort，這些O(nlogn)的排序演算法相比，Insertion Sort 不具有「遞迴」形式，因此不需要系統的 stack。
```
Insertion Sort 的原理為：
將第 i 個值加入「前 i − 1張排序過」的組合，得到 i 個排序過的值組合。
雖然有點饒口，但其實就是將 arr [ i ] 當成 key，
並在不斷比較 key 左邊的值後插在它該出現的地方，然後再去插入下個 key。
```
``` python
arr = [-4, 5, 78, 66, -12, 36, -24, 85, 13, 0]
def insertionSort(arr):
for i in range(1, len(arr)):
key = arr[i]
leftIndex = i - 1
while leftIndex >= 0 and arr[leftIndex] > key:
arr[leftIndex + 1] = arr[leftIndex]
leftIndex -= 1
arr[leftIndex + 1] = key
return arr
# [-24, -12, -4, 0, 5, 13, 36, 66, 78, 85]
```
## 介紹
在插入排序法中：
`for i in range(1, len(arr)):`
首先 arr [ 0 ] 被視為已排序好的陣列，所以迴圈初始值為 1，終止值為 len(arr)，也就剛好能將 arr 最後的值跑完
 
```key = arr[i]``` 將 arr [ i ] 視為要插入的值，宣告為 key
```leftIndex = i - 1``` 這是要跟 key 比較的值，也就是 key 左邊的 index
接下來跑 while 迴圈，如果 key 比 ```arr[leftIndex]``` 還小，就繼續往左邊比一個，直到找到該插入的位置
```arr[leftIndex + 1] = arr[leftIndex]``` 當 key 要往左繼續比，所以原來被比的值要往右放一格
 
找到 key 該插入的位置，或是比到 `leftIndex` < 0 ( 代表 key 值是當前最小 )，跳出 while 迴圈
`arr[leftIndex + 1] = key` 將原本的 key 放到要插入的位置
## BigO
從使用到的迴圈數量，可以推判插入排序法也不是效率佳的演算法，**但**
當問題的資料量較小時，使用 Insertion Sort 會很有效率，像是 python 的預設排序法 Timsort
先將資料分成些許小段落並進行 Insertion Sort，就代表插入排序法有它適合使用的狀況
Worst Case Performance: O(n^2)
Best Case Performance: O(n)
Average Performance: O(n^2)
 
## 參考資料：
[Comparison Sort: Insertion Sort(插入排序法)](http://alrightchiu.github.io/SecondRound/comparison-sort-insertion-sortcha-ru-pai-xu-fa.html)
[[演算法] TimSort — 以人命名的排序法](https://mailtojacklai.medium.com/%E6%BC%94%E7%AE%97%E6%B3%95-timsort-%E4%BB%A5%E4%BA%BA%E5%91%BD%E5%90%8D%E7%9A%84%E6%8E%92%E5%BA%8F%E6%B3%95-5d5e6ed7872c)
Udemy - 資料結構與演算法 (JavaScript)
點擊複製文章連結
X