编辑代码

var array = []

console.log('== 插入排序 ==\n')

console.log(`插入排序每次排一个数组项，以此方式构建最后的排序数组。假定第一项已经排序了，
接着，它和第二项进行比较，第二项是应该待在原位还是插到第一项之前呢？这样，头两项就已正确排序，
接着和第三项比较（它是该插入到第一、第二还是第三的位置呢？），以此类推。\n`)

function createRandomArray(size) {
    var arr = []
    for (let i = 0; i < size; i++) {
        arr.push(Math.round(Math.random() * size))
    }
    array = arr
    // return arr
}
/**
 * 思想：
 * 保存当前项；
 * 比较前一项和当前项j，如果前一项大则交换位置,j-- 继续向前比较 直至数组开头
 * 最后赋值j项数据为当前项
 * 结果：数组小的先移动到开头
 * - - - - - - - - 
 *           temp
 *      ->
 *  ->
 * temp
 */

function insertionSort() {
    var len = array.length, j, temp
    for (let i = 1; i < len; i++) {
        j = i
        temp = array[i] // 保存当前循环下标数据，用于位置交换
        console.log('外层--',i)
        // 前一项比当前项大
        // while (j > 0 && array[j - 1] > temp) {
        //     console.log('index',j)
        //     // 前面数据拷贝到后面
        //     array[j] = array[j - 1]
        //     j--
        // }

        for( j=i; j>0; j--){
            if(array[j - 1]>temp){
                array[j]=array[j - 1]
                // console.log('index',j)
            }else{
                break
            }
        }
        // 数据拷贝结束，对temp数据位置进行处理
        array[j] = temp
        // console.log('交换',array)

    }
}

// 位置交换
function swap(ind1, ind2) {
    var aux = array[ind1]
    array[ind1] = array[ind2]
    array[ind2] = aux
}

createRandomArray(8)
console.log('排序前：',array)
console.time('耗时')
insertionSort()
console.timeEnd('耗时')
// console.log(`时间复杂度：n^2`)
console.log('排序后：',array)

console.log(`\n 分析：
经过一轮外循环后最大数9以排至数组尾部，后续不用再对9进行比较,内层循环范围缩小至0-(n-1-i)\n`)