# 插入排序 (Insert sort)

## 簡介

可想像成撲克牌插入排序法

把 n 個待排序的元素看成為一個有序表和一個無序表，開始時有序表只包含一個元素，無序表中包含 n-1 個元素，排序過程中每次從無序表中取出第一個元素，把它依次與有序表元素的元素進行比較，將它插入到有序表中的適當位置，使之成為新的有序表。

## 舉例說明

假設今天有一陣列為 17, 3, 25, 14, 20, 9 ，我們需要利用插入排序法將之排序為由小到大：

1. 我們先將 17 設為有序表的第一個元素 (17), 3, 25, 14, 20, 9
2. 接著在無序表中取出第一個值，與有序表中的元素做比較，放置到合適的位置。
比如：3 < 17，所以將 3 置於 17 前方
4. 接下來是將 25 插入到有序表中，25 > 17 所以置於 17 後方

以此類推...


## 算法

### 詳細步驟

1. 需要進行 n-1 輪比較
2. 分為排序好的一邊和未排序好的一邊
3. 每輪從還沒排序的那邊拉出第一個值為插入目標
4. 在已經排序好的那一邊尋找，如果比較的目標比插入目標值大，就把**比較目標值**覆蓋到**比較目標值的後一位**，直到找到比插入目標小的值，或是索引為0為止。

## 時間複雜度
假設今天要對一陣列使用插入排序法由小到大排序。

### 最佳：O(1)
當資料順序恰好為由小到大時，每輪只需比較 1 次。
### 平均：O(n^2^)
第 n 筆資料，平均需要比較 `n/2` 次。
### 最差：O(n^2^)
當資料順序恰好為由大到小時，第 k 回合需比 k 次。

## 存在的問題

此時有一個陣列 arr = {2,3,4,5,6,1}，這時需要插入的數 1 為陣列中最小值，它所需要進行的過程為：

{2,3,4,5,6,6}
{2,3,4,5,5,6}
{2,3,4,4,5,6}
{2,3,3,4,5,6}
{2,2,3,4,5,6}
{1,2,3,4,5,6}

也就是說，當需要插入的數是較小的數時，後移的次數明顯增多，對效率有影響。

針對這個問題，有了更高效的插入排序改進版本—**希爾排序法(Shell Sort)**

## 參考資料
[插入排序法詳解](https://hackmd.io/@Aquamay/H1nxBOLcO/https%3A%2F%2Fhackmd.io%2F%40Aquamay%2FS1tJMC35_)