https://www.greatfrontend.com/questions/javascript/insertion-sort
Implement a function that performs an insertion sort. The function should take in an array of integers and return an array with the integers sorted in ascending order. The input array is modified.
Examples
insertionSort([9, 3, 6, 2, 1, 11]); // [1, 2, 3, 6, 9, 11]
insertionSort([12, 16, 14, 1, 2, 3]); // [1, 2, 3, 12, 14, 16]插入排序法
插入排序法是一個簡單的排序法，排序方式是將一個數逐個與前面的數比較，直到找到適合的位置，當所有數都逐個排序完畢則結束排序。
最基本的解法是使用兩個迴圈，第一個迴圈是遍歷第一位數到最後一位數，第二個迴圈則是遍歷已經排序過的數。不過通常會將第一位數視作已經排序過的數，所以實際上是從第二個數開始遍歷。
因此第一個迴圈的範圍為 1~arr.length，而第二個迴圈的範圍為 i - 1 ~ 0 (由後往前比較)。
比較兩數之後，如果當前的數比前一位數還要小，則要將兩數交換位置。
Solution
/**
* @param {Array<number>} arr The input integer array to be sorted.
* @return {Array<number>}
*/
export default function insertionSort(arr) {
let queue = arr;
for (let i = 1; i < arr.length; i++) {
for (let j = i - 1; j >= 0; j--) {
if (queue[j + 1] < queue[j]) {
let temp = queue[j + 1];
queue[j + 1] = queue[j];
queue[j] = temp;
}
}
}
return queue;
}
