实现原理

以下标1开始,向前比较,小于则交换
原理很像冒泡排序,只不过冒泡排序是两两比较,大的向后移。
而插入排序是无论什么时候,都只操作这一个数

插入排序.png

代码实现:

  for (let i = 1; i < arr.length; i++) { // 以第1(第0个数前面没有需要比较的)个数开始,直到数组跑完

    for (let k = i ; k > 0; k--) { // 依次与前面的进行比较。如 i=1时,依次与i-1比。i>0是因为i=0时,前面没有数比较了,所以不需要
      if (arr[k] < arr[k-1]) {
        array_swap(arr, k, k-1) // 交换位置
      } else {
        break;  // 由于是往前插入的,说明比当前值的都放到前面了,那么如果不比他小的值的地方是已经排好的了,所以可以直接跳出,这样才能满足最好时间复杂度O(n)
      }
      console.log('---第' + k + '次', arr)
    }
    console.log('第' + i + '次', arr)
  }
}

再优化的思路:

  1. 减少交换次数,比较大小后,记录想要插入的位置,后直接插入(不用交换)
  2. 交换使用位移运算的方式,优化数组的insert
  for (let i = 1; i < arr.length; i++) { // 以1 开始,循环
    let minPos = i // 当前数的下标
    let tmp = arr[i] // 当前数
    for (let k = i - 1; k > -1; k--) { // 遍历这个数以前的数
      if (tmp  < arr[k]) { // 用当前值去比较
        minPos = k
      } else {
        break;
      }
    }
    // 插入,前面的都往后移
    for (let j = i; j > minPos; j--) {
      arr[j] = arr[j - 1]
    }
    arr[minPos] = tmp 
  }

标签: none

添加新评论