插入排序-简单插入排序和二分插入排序

80 阅读 0 评论 53 点赞

我是靠谱客的博主漂亮煎饼，最近开发中收集的这篇文章主要介绍插入排序-简单插入排序和二分插入排序，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

插入排序：

插入排序（英语：Insertion Sort）是一种简单直观的排序算法。
它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

基本思想

每一步都是将待排序的一个数据，插入到一个已经有序的数据序列里面。直到所有的数据全部插入为止。【每一次插入都会进行一次排序】

类似于打牌【斗地主】，每摸一张就按照顺序放到位置。每摸一张牌之后一定是有序的，下一张牌来了，在已知的有序序列里面放到合适的位置。

插入排序方法

在插入 a[i]数据之前。a[0] ~a[i-1]一定是有序的。

现在需要插入a[i]这个数据，需要再a[0]~a[i-1]找到合适的位置放置a[i]，比如这个index为j，将a[i]放在索引j上面。

插入排序有多种：

1，简单插入排序 (每一次从后往前扫描每一个数据，确认插入位置的索引)


// 每一次插入，都与前面的【有序序列】比较，找到合适的位置
var simpleInsertSort = (arr) => {
  if (!arr || arr.length === 1) return arr
  let key, j;
  for (let i = 1; i < arr.length; i++) {
    key = arr[i];
    
    // 判定条件是，当前值小于index为j的值，并且不越界
    for (j = i - 1; j >= 0 && arr[j] > key ; j--) {
        arr[j+1] = arr[j]  
    }
    // 找到正确的位置之后，将这个值插入
    arr[j+1] = key
    
  }

  return arr
}

2，二分插入排序 (因为前面已经是有序的，确定位置可以用二分法来确定)

// 每一次插入，都与前面的【有序序列】比较，找到合适的位置
// 因为已知的序列是有序的，所以可以利用二分法寻找合适的插入位置
var binaryInsertSort = (arr) => {
  if (!arr || arr.length === 1) return arr
  let key;
  for (let i = 1; i < arr.length; i++) {
    key = arr[i];
    
    // 方法一： 简单查找，找到插入点
    // 判定条件是，当前值小于index为j的值
    // for (j = i - 1; j >= 0 && arr[j] > key ; j--) {
    //     arr[j+1] = arr[j]
    // }
    
    // 方法二： 二分查找，找到插入点
    let low = 0, high = i - 1;
    while(low <= high) {
      let mid = Math.trunc((low + high) / 2)
      if (arr[mid] > key) { // 这里大于小于就是排序的区别
        high = mid - 1
      } else {
        low = mid + 1
      }
    }

    // 找到了插入的位置是 high + 1
    // 后面的每一个往后面移动一个位置
    // 错误， 不能从前往后，这样j+1的值会丢失，【除非你用一个变量存取后面的值】
    // for(let j = high + 1; j < i - 1; j++ ) {
    //   arr[j+1] = arr[j]
    // }
    // 正确， 可以从后往前
    // 因为最后一个i的值已经存在key里面了，覆盖也没关系，
    for (let j = i - 1; j >= high + 1; j--) {
      arr[j + 1] = arr[j]
    }

    // 找到正确的位置之后，将这个值插入
    arr[high+1] = key
    
  }

  return arr
}