插入排序

基本排序-Insertion Sort

Insertion Sort

將資料分為兩區，前半部已排序，後半部的第一個值插入前半部適當的位置

原理

初始陣列： [2, 3, 4, 1, 5]

[2, 3, 4, 1, 5] 的 2 比較 3 => [2, 3]
[2, 3, 4, 1, 5] 的 2, 3 比較 4 => [2, 3, 4]
[2, 3, 4, 1, 5] 的 2, 3 ,4 比較 1
=> 先把 2, 3, 4 往後移 [2, 2, 3, 4 ,5]
=> 把 1 換到最前面 [1, 2, 3, 4, 5]

實現邏輯

設定target = i
從i+1往i~index=0找
如果找到，把i移到i+1，target設為i
把target的值換掉

插入排序法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
function insertion(arr) {
  for (let i = 1; i < arr.length; i++) {
    let currentVal = arr[i];
    let target = i;
    for (let j = i - 1; j >= 0 && arr[j] > currentVal; j--) {
      arr[j+1] = arr[j];
      target = j;
    }
    arr[target] = currentVal;
  }
  return arr;
}