二分查找

image.png
image.png
image.png
image.png
image.png

循环不变式

image.png

  1. // 二分查找
  3. function bsearch (A, x) {
  4.   let l = 0, // 查询结果的左边界
  5.     r = A.length - 1, //查询结果的右边界
  6.     guess //猜测位置
  7.   while (l <= r) {
  8.     guess = Math.floor((l + r) / 2)
  9.     //循环不变式
  10.     // guess等于 l和r的 中间位置
  11.     // l：查询范围左 ，r查询范围右
  12.     if (A[guess] === x) return guess
  13.     else if (A[guess] > x) r = guess - 1
  14.     else l = guess + 1
  15.     // 循环不变式
  16.     // l：新查找范围左 r：新查找范围右
  17.   }
  18.   return -1
  19. }
  21. const A = [3, 5, 19, 20, 44, 66, 90]
  22. console.log(bsearch(A, 22));
  23. console.log(bsearch(A, 5));
  24. console.log(bsearch(A, 20));

插入排序

3-5行 最坏情况 ，就需要 几何倍的计算
image.png

// 插入排序
// 从前往后开始遍历，但是比较插入的时候，要从后往前一一比较然后插入
function insert (A, i, x) {
  // p 指向下一个需要比较的元素
  // p+1指向空位 
  let p = i - 1
  while (p >= 0 && A[p] > x) { // 如果A的当前项 大于了 x，就说明需要给他让位置
    A[p + 1] = A[p]
    p--
  }
  A[p + 1] = x
}

function insertion_sort (A) {
  for (let i = 0; i < A.length; i++) {
    insert(A, i, A[i])
  }
}

const B = [19, 3, 5, 44, 66, 20, 90]
// insertion_sort(B)
console.log(B);

冒泡排序

function swap (A, i, j) {
  const t = A[i]
  A[i] = A[j]
  A[j] = t
}
function bubble_sort (A) {
  // 外层 i控制对大值的位置 ，会递减 也就是说每一轮完成后，已确定最大值的位置就要减一
  for (let i = A.length - 1; i >= 1; i--) {
    // 循环结束j指向A[0]-A[j] 中的最大值
    for (let j = 1; j <= i; j++) {
      A[j - 1] > A[j] && swap(A, j - 1, j)
    }
    // 循环结束后 A[i] - A[n-1] 已排序
  }
}
const B = [19, 3, 5, 44, 66, 20, 90]
bubble_sort(B)
console.log(B);

合并排序

image.png

image.png

function merge (A, p, q, r) {
  const A1 = A.slice(p, q)
  const A2 = A.slice(q, r)
  A1.push(Number.MAX_SAFE_INTEGER)
  A2.push(Number.MAX_SAFE_INTEGER)
  for (let k = p, i = 0, j = 0; k < r; k++) {
    A[k] = A1[i] < A2[j] ? A1[i++] : A2[j++]
  }
}
function merge_sort (A, p, r) {
  if (r - p < 2) { return }
  const q = Math.ceil((p + r) / 2)
  merge_sort(A, p, q)
  merge_sort(A, q, r)
  merge(A, p, q, r)
}
merge_sort(B, 0, B.length)
console.log(B);