Insertion Sort (插入排序法) 的原理也很直觀，將要排序的元素插入已經排列好的左側陣列：
1. Insertion Sort 原理解釋
▲ 將第一個元素視為已經排列好的陣列，因此第一輪從 i = 1 開始跑
▲ 如果待排序的元素比排列好陣列中的最後一個元素還小，代表需要將待排序元素插入已經排序好的陣列中
接著要判斷要插入到排列好陣列中的哪個位置：
第二輪 (i = 2)：
第三輪 (i = 3)
2. JavaScript 實作
function insertionSort(arr) {
const n = arr.length;
for (let i = 1; i < n; i++) {
// 尚未排列的第一個元素
const currElement = arr[i];
// 已經排列好的陣列中最後元素的 index
let j = i - 1;
// 目標元素要小於已經排列好的陣列中最後的元素，才會進到此迴圈
while (j >= 0 && currElement < arr[j]) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = currElement;
}
return arr;
}概念圖：
3. Time Complexity
最佳：O(n)
最差：O(n2)
平均：O(n2)
