前端-折半插入排序

1. 折半插入排序
   • 先使用二分法查找出该插入的位置, 再进行移动

function ZheBanSort(arr) {
  const len = arr.length;
  let i, j, low, high, mid, temp;
  // 首先找到插入点 二分法
  for (i = 1; i < len; i++) {
    // 保存当前元素
    temp = arr[i];
    low = 0;
    high = i - 1;
    // 依次将A[1]~A[n-1] 插入到`前面已经排好序`的数组中
    while (low <= high) {
      // 不能直接使用3/2 因为3/2=1.5
      mid = parseInt((low + high) / 2)
      if (arr[mid] > temp) {
        high = mid - 1
      } else {
        low = mid + 1;
      }
    }
    // 统一往后移动元素
    for (j = i - 1; j >= high + 1; j--) {
      arr[j + 1] = arr[j]
    }
    arr[high + 1] = temp;
  }
}

const a = [5, 2, 4, 3, 8, 6, 9, 0, 1, 7];
ZheBanSort(a)
console.log(a)