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

亦凉 2022-12-12 13:58 209阅读 0赞

### 插入排序： ###

插入排序（英语：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
    }