js数组插入排序(优化技巧)

插入排序的基本写法如下：

function insertSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let key = arr[i]
    let j = i - 1;
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j]
      j--;
    }
    arr[j + 1] = key
  }
  return arr
}

怎么优化插入排序呢？因为每次都要维护一个已排序的列表，如果有新的元素进来，就要依次对比大小，关于查找我们的优化策略是通过二分查找的方法找到元素需要插入的位置即可。

function insertSort (arr) {
  let first = arr[0]
  let result = first ? [first] : [];
  for (let i = 1; i < arr.length; i++) {
    let key = arr[i]
    insert(result, key)
  }
  return result;
}
function insert(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  while (left <= right) {
    let mid = (left + right) >> 1;
    if (target < arr[mid]) {
      right = mid - 1
    } else {
      left = mid + 1
    }
  }
  arr.splice(right + 1, 0, target)
  return arr
}