插入排序

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)
        }