# 经典排序算法-03-插入排序

function insertSort(arr) {
    if(!arr.length) return []
    if(arr.length === 1) return arr

    // 将等待排序数组的元素逐个插入到目标数组中
    // 首个元素无需比较，直接插入
    const arrRet = [arr[0]]

    // 首个元素之后的逐个与目标数组中的元素进行比较
    for (let i = 1; i < arr.length; i++) {
        
        const numToInsert = arr[i];
        let count = arrRet.length

        for (let j = 0; j < count; j++) {
        
            const numSorted = arrRet[j];
        
            console.log(`[${i}--${j}]--Result:`,arrRet)
        
            // 如果新元素小于目标数组中的某一个元素，则插入
            if(numToInsert < numSorted) {
                arrRet.splice(j, 0, numToInsert)
                break
            }
            // 如果新元素大，比对到末尾都没能插入，直接添加到目标数组末尾
            if(j === count - 1) {
                arrRet.push(numToInsert)
                // break
            }
        }
    }
    return arrRet
}

const nums = [3,5,9,7,4,2,10]
const ret = insertSort(nums)
console.log('[Final Result]:', ret)

/**
 * 
[1--0]--Result: [ 3 ]
[2--0]--Result: [ 3, 5 ]
[2--1]--Result: [ 3, 5 ]
[3--0]--Result: [ 3, 5, 9 ]
[3--1]--Result: [ 3, 5, 9 ]
[3--2]--Result: [ 3, 5, 9 ]
[4--0]--Result: [ 3, 5, 7, 9 ]
[4--1]--Result: [ 3, 5, 7, 9 ]
[5--0]--Result: [ 3, 4, 5, 7, 9 ]
[6--0]--Result: [ 2, 3, 4, 5, 7, 9 ]
[6--1]--Result: [ 2, 3, 4, 5, 7, 9 ]
[6--2]--Result: [ 2, 3, 4, 5, 7, 9 ]
[6--3]--Result: [ 2, 3, 4, 5, 7, 9 ]
[6--4]--Result: [ 2, 3, 4, 5, 7, 9 ]
[6--5]--Result: [ 2, 3, 4, 5, 7, 9 ]
[Final Result]: [ 2, 3, 4, 5, 7, 9, 10 ]
 */