lgn！ lgn阶乘 <= nlgn

推导公式如下

快速排序

// 快速排序
function swap (A, i, j) {
  [A[i], A[j]] = [A[j], A[i]]
}
function partition (A, lo, hi) { // A数组 lo起始位置 hi结束位置
  let pivot = A[hi - 1]
  let i = lo, j = hi - 1
  // 小于中心的范围 [lo,pivot)
  // 大于中心得范围 [j,hi-1)
  // 结束条件 i==j
  // 未确定范围[i,j)
  while (i !== j) {
    if (A[i] <= pivot) {
      i++
    } else {
      swap(A, i, --j)
    }
  }
  // 最后结束后，还有中心点进行交换
  swap(A, j, hi - 1)
  return j
}
function qsort (A, lo = 1, hi = A.length) {
  if (hi - lo <= 1) return
  const p = partition(A, lo, hi)
  qsort(A, lo, p)
  qsort(A, p + 1, hi)
}
const C = [10,50,30,90,40,80,70]
qsort(C)
console.log(C);

记数排序

时间复杂度 O(n)
空间复杂度 O(n)

1.循环遍历一下数组A
2.找出原数组A得最大值然后把他+1
3.创造一个比最大值多1 得长度得数组
4.然后遍历出每一项出现得次数，让他得对应下标++

5.累计数组B从左到右用自己当前值，加前一个位置得数，比如现在i=5 所在得位置就应该是 5+1 = 6

6.在往回填值得时候，就需要在原数组中取值，然后在累计数组中找到对应得位置，如图i=6，得时候 6得位置原来是7，7-1得位置就应该是 6 要放入得位置，然后5 也是5这里是 6 ，6-1 也就放到 5 得位置
7.下图中 3 得位置原来是 5 ，5-1 要放入 4 得位置，然后要让累计数组中的位置— ，防止接下来还有3，遍历得时候接下来，确实有个3 ，3就放在4-1点得位置就是 3
8.继续循环直到结束

// 计数排序
function counting_sort (A) {
  const max = Math.max(...A)
  //累计数组
  const B = Array(max + 1).fill(0)
  //结果数组
  const C = Array(A.length)
  // 累计位递增
  A.forEach((_, i) => B[A[i]]++)
  // 累计求和
  for (let i = 1; i < B.length; i++) {
    B[i] = B[i - 1] + B[i]
  }
  // 结果取出
  for (let i = 0; i < A.length; i++) {
    const p = B[A[i]] - 1 //回写位置
    B[A[i]]--
    C[p] = A[i]
  }
  return C
}
const C = [10, 50, 30, 90, 40, 80, 70]
console.log(counting_sort(C));

基数排序

队列先进先出

栈先进后出

// 基数排列
function radix_sort (A) {
  const max = Math.max(...A)
  const buckets = Array.from({ length: 10 }, () => [])
  // 有效数位
  let m = 1
  // 如果当前位数小于最大的数,就需要循环
  while (m < max) {
    // 将数组放到桶中
    A.forEach(number => {
      // 求出当前位数
      const digit = ~~((number % (m * 10)) / m)
      buckets[digit].push(number)
    })
    // 从桶中取元素
    let j = 0
    buckets.forEach(bucket =>{
      while(bucket.length>0){
        A[j++] = bucket.shift()
      }
    })
    // 下一个位置
    m *= 10
  }
}
const C = [10, 50, 30, 90, 40, 80, 70]
radix_sort(C)
console.log(C);

桶排序

// 桶排序
function insertion_sort_t (A) {
  for (let i = 1; i < A.length; i++) {
    let p = i - 1
    const x = A[p + 1]
    while (p >= 0 && A[p] > x) {
      A[p + 1] = A[p]
      p--
    }
    A[p + 1] = x
  }
}
function bucket_sort (A, k, s) {
  const buckets = Array.from({ length: k }, () => [])
  // 放入桶中
  for (let i = 0; i < A.length; i++) {
    const index = ~~(A[i] / s)
    buckets[index].push(A[i])
  }
  // 排序每个桶
  for (let i = 0; i < buckets.length; i++) {
    insertion_sort(buckets[i])
  }
  // 取出每个同
  return [].concat(...buckets)
}
const C = [10, 50, 30, 90, 40, 80, 70]
console.log(bucket_sort(C, 10, 10));

外部排序

分开每一步，来进行处理

如果到时候每一组的数据比较多的时候，就要考虑使用什么排序算法，如果插入排序，就有可能 o（n2）的，就会跑不完，如果是快排，就需要空间占用多一些，所以需要，到时候实际考虑一下怎么处理

全栈算法

0209有序排序