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