js 实现插入排序

// 插入排序的原理：
// 一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法 。
// 插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增 1 的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动 。
// 稳定性：插入排序是判断当元素小于才进行交换，所以为稳定排序
// 冒泡排序是两个两个交换
// 选择排序是每一个和无序数列中的起始位置进行交换
// 插入排序是每一个无序数列中的元素分别和有序数列中的每一个进行对比和交换，直到遇到比他小的，则停止交换，插入该元素
// 每次都进行两两交换版本
function insertSort(arr) {
    if (arr.length < 2) {
        return arr;
    }
    // 定义 count 代表执行了趟循环
    let count = 0;
    // i 代表每趟循环，获取的无序数列的其实位置，从第一位开始
    for (let i = 1; i < arr.length; i++) {
        count++;
        // 提前存下无序数列中的其实值，作为待插入值，此时 i=j+1
        let inertValue = arr[i];
        // 从右向左遍历有序数列，有序数列的起点是第 0 位，终点是无序数列前一位，即 i-1
        for (let j = i - 1; j >= 0; j--) {
            const temp = arr[j];
            // 如果要插入的元素小于当前位置元素  交换两个元素位置
            if (inertValue < arr[j]) {
                arr[j] = inertValue;
                // inertValue每次插入后会改变该值的索引，所以
                arr[j + 1] = temp;
            }
        }
    }
    console.log(`执行了${count}趟循环`);
    return arr;
}
console.log("直接插入排序");
console.log(insertSort([6, 3, 2, 1, 6, 3, 7, 8, 2, 4, 0, 1, 6, 5])); // 执行了13趟循环
console.log(insertSort([6, 3, 7, 8, 2, 4, 0, 1, 6, 5])); // 执行了9趟循环
console.log(insertSort([1, 2, 3, 4, 5, 6, 7, 8, 9, 9])); // 执行了9趟循环
// 优化版：先将需要移动的元素位置一一变更，最终找到需要插入的位置，直接插入
function insertSort2(arr) {
    if (arr.length < 2) {
        return arr;
    }
    // 定义 count 代表执行了趟循环
    let count = 0;
    for (let i = 1; i < arr.length; i++) {
        count++;
        // 暂存当前待插入元素
        let insertValue = arr[i];
        let j = i - 1;
        // 循环执行的条件是当前插入的元素小于当前遍历到的元素
        for (; j >= 0 && insertValue < arr[j]; j--) {
            // 之所以可以始终后移，不怕覆盖最后一位元素，是因为最后一位即为待插入元素的位置
            arr[j + 1] = arr[j]; // 如果 当前插入的元素小于当前遍历到的元素，则将该位置元素后移
        }
        // 最终循环终止时，j 即为当前待插入元素的位置
        // insertValue的值插入适当位置
        arr[j + 1] = insertValue;
    }
    console.log(`执行了${count}趟循环`);
    return arr;
}
console.log("直接插入排序2");
console.log(insertSort2([6, 3, 2, 1, 6, 3, 7, 8, 2, 4, 0, 1, 6, 5])); // 执行了13趟循环
console.log(insertSort2([6, 3, 7, 8, 2, 4, 0, 1, 6, 5])); // 执行了9趟循环
console.log(insertSort2([1, 2, 3, 4, 5, 6, 7, 8, 9, 9])); // 执行了9趟循环