插入排序是一种将指定元素与某个有序区域元素比较并交换位置的排序算法。
我们先简单举个例子,假设现在有这样一个无序数组
首先,我们把索引为0的元素看作区域,该区域是有序的,因为就只有一个元素,怎样排序都是它一个元素,所以就认为它是有序的。
然后我们取出有序区域右边的第一个元素,即索引为1的元素 67,存到变量 temp 中。然后从有序区域的最右边开始,将元素依次与变量 temp 中的元素 67 比较,若大于67,则将位置向右移动一格;若小于67,则不需要继续遍历了,因为该区域是有序的。
上代码:
function insertSort(arr){
let length = arr.length;
for(let i=1; i<length; i++) {
let temp = arr[i];
let j = i;
while(arr[j-1] > temp && j>0) {
arr[j] = arr[j-1];
j--;
}
// 将temp插入到合适的位置
arr[j] = temp;
}
return arr;
}
console.log(insertSort([46,32,38,22,44,16]));
VM77562:15 (6) [16, 22, 32, 38, 44, 46]