插入排序

• 时间复杂度： O(n²)
• 空间复杂度： O(1)

function swap(arr, index1, index2) {
    var temp = arr[index1];
    arr[index1] = arr[index2];
    arr[index2] = temp;
}

var initArr = [9,8,7,6,5,4,3];


// 缺点： 不停的swap影响性能
function insertSort(arr) {
    
    var len = arr.length;

    // 边界情况
    if (len < 2) {
        return arr;
    }

    for(let i = 1; i < len; i ++) {
        for (var j = i; j > 0; j --) {

            if (arr[j - 1] > arr[j]) {
                swap(arr, j , j - 1);
            }
        }
    }

    console.log(arr);
}
console.time('优化前');
insertSort(window.testArr);
console.timeEnd('优化前');
console.log(window.count);

理论上的优化

// 优化： 利用覆盖原则，只swap一次
function swap(arr, index1, index2) {
    var temp = arr[index1];
    arr[index1] = arr[index2];
    arr[index2] = temp;
}

var initArr = [9, 8, 7, 6, 5, 4, 3];


function insertSort(arr) {
    var len = arr.length;

    if (arr.length < 2) {
        return arr;
    }

    for (let i = 1; i < len; i++) {
        var iIndex = i;
        var moveIndex = i - 1;
        var temp = arr[i];
        // var flag = true;
        // debugger;
        // debugger;
        if (arr[iIndex] > arr[moveIndex]) {
            continue;
        }

        //333
        for (let j = i; j > - 1; j--) {
            if (arr[j - 1] < temp) {
                arr[j] = temp;
                break;
            }

            if (!arr[j - 1]) {
                arr[j] = temp;
                break;
            }

            arr[j] = arr[j - 1];
        }

    }
    console.log(arr)
}

console.time('优化后');
insertSort(window.testArr);
console.timeEnd('优化后');
console.log(window.count);