插入排序（Selection Sort）基本思想：
插入排序每次排一個數組項，以此方式構建最后的排序數組。假定第一項已經排序了，接著，
它和第二項進行比較，第二項是應該待在原位還是插到第一項之前呢？這樣，頭兩項就已正確排
序，接著和第三項比較（它是該插入到第一、第二還是第三的位置呢？），以此類推。
代碼實現
function insertSort(arr) {const len = arr.length;let j, tmp;//默認第一項已經排序for (let i = 1; i < len; i++) {j = i;//臨時記錄的變量temp = arr[i];//比較while (j > 0 && arr[j - 1] > temp) {arr[j] = arr[j - 1];j--;}//插入arr[j] = temp;}return arr;
}
復雜度
- 空間復雜度(O(1)),也是一種原址比較
- 時間復雜度O(n2)
代碼測試
var arr = [1, 67,45,30, 89, 10,23];const ret = insertSort(arr);console.log("🚀 ~ ret:", ret)
