Skip to main content

插入排序

算法模式：双指针-快慢指针​

时间复杂度：O(n²)

思路：向前比较

  1. 防御性：长度小于 1 直接返回

  2. 下一位:外层 for 从 0 递增

    • 记录下一位：index = i

  3. 上一位:内层 for 从 i-1 递减

  4. 比较 arr[i] < arr[j]

  5. splice 插入排序

    • arr.splice(index,0,arr[i])
    • arr.splice(i+1,1)
function insertSort(arr) {
    if(arr.length <=1) return arr;

    for(var i = 1; i < arr.length; i ++){
        // 后一位数
        index = i;
        // 前一位数
        for(var j = i - 1; j >= 0; j--){
            // 后一位数 比较 前一位数
            if(arr[i] < arr[j] ){
                // 下标交换
                index = j;
            }
        }
        /* 交换位置 */
        // 新增并插入：改变原数组
        arr.splice(index,0,arr[i]);
        // 删除：旧数据
        arr.splice(i+1,1);
    }
  return arr
}

const arr = [5,4,3,2,1]
console.log(insertSort(arr))

参考​