算法学习-排序-插入排序

原理

    直接插入排序的基本思想：每次将一个待排序的记录，按其keyword的大小插入到前面已经排好的子序列中的适当位置，直到所有记录插入完毕为止。

实现

    假设数组为A[0...n-1]，

    1.初始时，A[0]自成1个有序区,无序区为A[1....n-1]。令i = 1；

    2.将A[i]并入当前的有序区A[0...i-1]中形成A[0...i]的有序区间；

    3.i++并反复第二步直到i == n-1，至此排序完毕。

效率分析

    稳定

    空间复杂度O(1)

    时间复杂度O(n2)

    最差情况：反序。须要移动n*(n-1)/2个元素

    最好情况：正序，不须要移动元素

    数组已是排序或者接近顺序。插入排序的效率最好的情况是O(n)，最坏的情况执行时间和平均情况执行时间均为O(n2)

    通常插入排序呈现出二次排序算法中的最佳性能。

JavaScript

let arr1 = [2, 8, 3, 89, 67, 45]

function insertSort(arr){

  let newArr = []

  if(Array.isArray(arr) && arr.length>0){

    newArr = newArr.concat(arr)

    for(let i=0; i < arr.length; i++){

      let j = i

      let current = arr[i]

      while(j>0 && current < newArr[j-1]){

        newArr[j] = newArr[j-1]

        j--

      }

      newArr[j] = current

    }

  }

  return newArr

}

console.log('reArr===>', insertSort(arr1))