今天要介紹的是插入排序法 Insertion Sort，在排序小型資料時，此演算法效能比氣泡排序和選擇排序效能更好。

插入排序法運作方式為逐一將資料值加入已排序的資料列，並根據加入的資料值插入到資料列的某個位置。

此網頁有小動畫可以參考看看，非常淺顯易懂:
http://notepad.yehyeh.net/Content/Algorithm/Sort/Insertion/1.php

接著我們來實作吧!完成後會討論其時間複雜度~

1. 首先建立一個 insertionSort() 的函式，接著建立一層迴圈， i 要從1開始，為資料列的第二個數，前面的一個數視為已排序的資料列

2. 接著宣告兩個變數 current 和 j ，分別儲存要加入排序的值和已排序好的資料列中最後一個值的索引值

3. 透過 while 迴圈，當 j >= 0 ，表示還沒排序到資料列第一個值而且加入排序的值比排序好的資料列中最後一個值小時，current < data[j]，就進入迴圈

4. 在迴圈中，我們將前面的值傳給後面一個位置的值，以 [1, 234, -5] 為例:
   經過 while 迴圈一次運算後變成 [1, 234, 234]，j = 0，由於 j>= 0 且 -5(current) < 1(data[j]) ，可再進入 while 迴圈一次，變成 [1, 1, 234]

5. 最後跳出 while 迴圈時，將原本存好的值 current(-5) 指定給 data[j + 1] ，此時的 j 為兩種可能:

• 第一為 0
• 第二為 current < data[j] 此條件不成立時，不知道 j 已經被減幾次故不知道 j 的值

6. 在 [1, 1, 234] 的範例裡，j 為0，因此最後結果就是變成 [-5, 1, 234]

function insertionSort(data) {
  const length = data.length;
  for (let i = 1; i < length; i++) {
    let current = data[i]; // 要加入排序的值
    let j = i - 1; // 為已排序好的資料列中最後一個值的索引值
    while (j >= 0 && current < data[j]) {
      data[j + 1] = data[j];
      j--;
    }
    data[j + 1] = current;
  }
  console.log(data);
}

insertionSort([1, 234, -5, 78, -182, 45]);

透過 console.log(data); 可以看到排序過程:

時間複雜度:

• 最佳時間複雜度：O(1)
  當資料列已經是完成排序的狀態

• 平均時間複雜度：O(N^2)
  第n筆資料，平均比較n/2次

• 最差時間複雜度：O(N^2)
  當資料的順序恰好和目標排序的順序相反，第 i 回合需比 i 次

本次程式碼在以下連結:
https://github.com/a90100/javascript-data-structure/blob/master/day19-insertion-sort.js

明天將會介紹第四種排序法，合併排序法!