前端提高算法的意义

1.流畅问题
动画 ，1秒60帧，同时有可能还在执行，请求或者别的操作，如果写的不好的话，就可能让用户感觉到卡顿
2.新老机型
前端有大量机型需要适配，这些机型可能没那么好，同一段代码，老机器有可能会 跑挂掉，产生雪崩

前置知识

原生数组的sort是 c++写的 ，运行速度比较块，节省10倍左右

算法复杂度

一般我们都说的 是渐进上界 ，一般就是最坏的情况，就是 O(n) 一般就是说 一个循环 ，O(n ^ 2) 就是两个循环

大数定理

实现一个 生成100万随机打乱函数

function gen (w) {
  const arr = []
  for (let i = 0; i < w * 10000; i++) {
    arr[i] = i + 1
  }
  shuffle(arr)
  return arr
}
// 打乱算法 这个会慢一些 ，也不一定准确
function shuffle_simple (arr) {
  return arr.sort(() => Math.random() - .5)
}
gen(100)

循环不变式

每次循环结束，存在一个已经排序的列表和没有排列的列表。j指向下一个未排序的数字

插入排序

最好情况 ：所有正序O(N)
最坏情况： 所有倒序O(N^2) 这种情况就要注意了，如果数量级一上去，就有可能会很长时间跑不完
平均情况 n^2

function insertion_sort (A) {
  for (let j = 0; i < A.length; j++) {
    const key = A[j]
    let i = j - 1
    while (i >= 0 && A[i] > key) {
      A[i + 1] = A[i]
      i--
    }
    A[i + 1] = key
  }
}
// 最好 O(N)
// 最坏 O(N^2)

算法优化思路

合并排序

如下图： 原来要解决 1024 级别的问题，现在经过拆分就可以把原来的复杂度进行降低

// 哨兵
// 也就是在输入的最后一项加入一个 js的最大值
// 这样就不需要总判断js的length是不是没有了
const SENTINEL = Number.MAX_SAFE_INTEGER

// 这个函数复杂度
// (log2 1024) - 1 = 9
// 2 ^ 10 = 1024
// 1og2 1024 = 10
function divide (p, r) {
  return Math.floor((p + r) / 2)
}
function conquer (A, p, q, r) {
  const A1 = A.slice(p, q)
  const A2 = A.slice(q, r)
  A1.push(SENTINEL)
  A2.push(SENTINEL)
  // i++ 是后序执行的，所以就先赋值后相加
  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 = 0, r, l) {
  r = r || A.length
  if (r - p === 1) { return }
  if (r - p === 2) {
    if (A[p] > A[r - 1]) {
      [A[p], A[r - 1]] = [A[r - 1], A[p]]
    }
    return
  }
  const q = divide(p, r)
  merge_sort(A, p, q, l + 1)
  merge_sort(A, q, r, l + 1)
  conquer(A, p, q, r)
}
let A = [111,2,3,5,6,19]
merge_sort(A)

快速排序的循环不变式
i 指向小于支点的最后一个
j 指向未确认的每一个

function swap (A, i, j) {
  [A[i], A[j]] = [A[j], A[i]]
}

function divide (A, p, r) {
  // p是从几开始，r是到几结束
  const x = A[r - 1]
  let i = p - 1
  for (let j = p; j < r - 1; j++) {
    if (A[j] < x) {
      i++
      swap(A, i, j)
    }
  }
  swap(A, i + 1, r - 1)
  return i + 1
}
function qsort (A, p = 0, r) {
  r = typeof r !== 'undefined' ? r : A.length
  if (p < r - 1) {
    const q = divide(A, p, r)
    qsort(A, p, q)
    qsort(A, q + 1, r)
  }
}

let A = [4,3,2,1]
qsort(A)
console.log(A)