簡(jiǎn)述
插入排序（Insertion-Sort）的算法描述是一種簡(jiǎn)單直觀的排序算法痘绎。它的工作原理是通過構(gòu)建有序序列，對(duì)于未排序數(shù)據(jù)帚桩，在已排序序列中從后向前掃描纤怒，找到相應(yīng)位置并插入。插入排序在實(shí)現(xiàn)上，通常采用in-place排序（即只需用到O(1)的額外空間的排序）克滴，因而在從后向前掃描過程中逼争，需要反復(fù)把已排序元素逐步向后挪位，為最新元素提供插入空間劝赔。
算法思想
1誓焦、先拿到第一個(gè)元素，認(rèn)為它是已排序的
2着帽、拿到下一個(gè)元素a杂伟，與已排序序列從后往前相比
3、如果已排序序列中的元素大于a仍翰，則將它的位置往后移一位
4赫粥、重復(fù)2，3步驟歉备，知道已排序序列中的元素小于等于a
5傅是、將a插入到4布中元素后
圖解
image.png
js實(shí)現(xiàn)
let arr = [5,3,7,2,6];
//插入排序
function insertSort(arr) {
for (let i = 1; i < arr.length; i++) {
//當(dāng)前要處理的數(shù)
let temp = arr[i];
let j = i - 1;
while (j >= 0 && arr[j] > temp) {
//如果前一個(gè)數(shù)大于后一個(gè)數(shù),將前一個(gè)數(shù)往后移一位
arr[j + 1] = arr[j]
j--
}
//此時(shí)的j是要處理的數(shù)排序后應(yīng)該在的位置
arr[j+1] = temp
}
return arr;
}
console.log("插入排序arr", insertSort(arr))
