1.循环将数组分成两个区域，排序区和未排序区域，每一轮从未排序区域取出来一个值，插入到排序区域
2.优化：待插入元素进行比较时，遇到比自己小的元素，就代表找到了插入位置，无需进行后续比较
注意：插入事直接移动元素，而不是交换元素
window.onload = function() {
var arr = [2,4,9,1,7,3,6,8,5]
// 插入排序
insertSort(arr)
}
// 插入排序
function insertSort(arr) {
for (let i = 1; i < arr.length; i++) {
// 记录待插入的元素值
var tmp = arr[i]
// 代表已排序区域的元素索引
var j = i - 1
console.log(`第${i}轮循环`)
while (j >= 0) {
console.log(`~~~第${j}次比较~~~~~`)
// 当待插入值小于已排序区域的值时,就代表找到了插入位置
if (tmp < arr[j]) {
arr[j + 1] = arr[j]
} else {
// 退出当前循环,减少比较次数
break
}
j--
}
arr[j+1] = tmp
}
console.log(arr)
}
