插入排序(希尔排序与直插排序)
1.插入排序：插入排序的工作原理就是将未排序数据，对已排序数据序列从后向前扫描，找到对应的位置并插入。插入排序通常采用占位的形式，空间复杂度为O(1),因此，在从后向前扫描的过程中，需要反复的把已排序的元素逐步向后挪位，为新插入元素提供插入的位置。
const insertionSort = (nums) => {
for (let i = 1; i < nums.length; i++) { let j = i - 1 let tmp = nums[i] while (j >= 0 && nums[j] > tmp) {
nums[j + 1] = nums[j]
j--
}
nums[j+1] = tmp
}
return nums
} 2.希尔排序：希尔排序本质上是一种插入排序，但是对数列进行了等间隔分组处理，在每一组中做插入排序，这一优化使得时间复杂度降到了O(n^2)以下。
function shellSort(arr) {
let len = arr.length;
// gap 即为增量
for (let gap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2)) {
for (let i = gap; i < len; i++) {
let j = i;
let current = arr[i];
while(j - gap >= 0 && current < arr[j - gap]) {
arr[j] = arr[j - gap];
j = j - gap;
}
arr[j] = current;
}
}
}
var arr = [3,5,7,1,4,56,12,78,25,0,9,8,42,37];
shellSort(arr);