排序算法介绍(JavaScript)-一一网

引入

将无序状态的一列数据转化为有序状态。如：

数字顺序：5，8，12，23，30，56，68，…..

字典顺序：an，boy，cow，yellow，…..

实现

二分查找(binary search)

想象: 如果你是一名老师，在一堆试卷中，你想要找出某张试卷，你会怎么去做，才能在最短的时间里找到它。

抽象

   function bsearch(A, x)

    A：数组
    x：需要查找的值
    返回：x 在 A中的位置，不存在返回 -1
复制代码

循环不变式

    循环前：
        l 表示：查找范围的左边界
        r 表示：查找范围的右边界
        guess 表示：l，r 的中间位置

    循环后：
        l 表示：新的查找范围的左边界
        r 表示：新的查找范围的右边界
        guess 表示：新的l，r中间位置  

    每次循环结束后，查找的值要么在位置 l-r 之间，要么不存在      
复制代码

程序实现

    // 在一组已经排序好的数中查找，如果找到那就返回索引 未找到返回 -1
    function bSearch(A, x) {
    let l = 0,
        r = A.length - 1,
        guess
    while(l <= r) {
        guess = Math.floor((l + r)/2)
        
        if(A[guess] === x) return guess
        else if(A[guess] < x) l = guess + 1
        else r = guess - 1
    }
    return -1    
}

let arr = [1, 2, 5, 11, 12, 16]
console.log(bSearch(arr, 11)) // 结果是：3
复制代码

插入排序(insert sort)

可以想象：假如你的手上的牌是有序的，每次抓一张插入对应的位置。

问题:如何在一个有序的数组中，插入一个新值，后任然是有序的

函数抽象

  function insert(A, x)
  A: 已排序的数组
  x: 需要插入的元素
  返回值： 无
复制代码

第一版：

  const A = [2, 4, 7, 9, 13] /** 原数组 */
  const x = 8 /** 需要插入的元素 */
  const index = A.indexOf(b)
  A.splice(index === -1 ? A.length : index, 0, x)
  console.log(A) // [2, 4, 7, 8, 9, 13]
复制代码

循环不变式

p: 指向下一个要比较的元素
p+1: 指向腾出来的空位

i: 指向下一个需要排序的元素
复制代码

第二版：

  function insert(A, i, x) {
    let p = i - 1
    while(A[p] > x) {
      A[p + 1] = A[p]
      p--
    }
    A[p + 1] = x
  }

  function insert_sort(A) {
    for (const i of A.keys()) {
      insert(A, i, A[i])
    }
  }
  const  A = [1, 2, 100, 11, 12, 16]
  insert_sort(A)
  console.log(A) // [1, 2, 11, 12, 16, 100]
复制代码

冒泡排序(bubble sort)

可以想象，在一个湖面下，有一串大小不一的气泡正在往上面冒，那么它们谁会最先到达水平呢根据物理学原理是体积最大的那个最先到水面

问题：根据冒泡的原理实现排序…

问题抽象：

  function bubble_sort(A)
  A: 需要排序的数组
  返回：无
复制代码

循环不变式

  外层循环不变式:

  第 k 次循环执行后，前 k 大的值顺序排序在位置 i 。
  循环执行后， 位置 i 以及它右边的值处于排序的状态

  内层循环不变式:

  每次循环结束时控制变量 j 指向 0-j 元素中最大的值
复制代码

程序实现：

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

  function bubble_sort(A) {
    for (let i = A.length; i >= 1; i--) {
      for (let j = 1; j <= i; j++) {
        A[j - 1] > A[j] && swap(A, j - 1, j)
      }
    }
  }
  const A = [1, 2, 100, 11, 8, 16]
  bubble_sort(A)
  console.log(A) //[ 1, 2, 8, 11, 16, 100 ]
复制代码

合并排序(merge sort)

问题：实现将原数组不断拆分，然后再进行合并

问题抽象：

  function merge(A, p, q, r)
  
  A: 数组
  p: 左半边开始位置
  q: 左半边结束，右半边开始位置
  r: 右半边结束
复制代码

循环不变式：

  i: 指向A1中下一个要被放回的元素
  j: 指向A2中下一个要被放回的元素
  k: 指向A中下一个回写的位置
复制代码

程序实现：

  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
    let q = Math.ceil((r + p)/2)
    merge_sort(A, p, q)
    merge_sort(A, q, r)
    merge(A, p, q, r)
  }
  const A = [1, 2, 60, 19, 8, 16]
  merge_sort(A) // [ 1, 2, 8, 16, 19, 60 ]
  merge_sort(A, 3, 5) // [ 1, 2, 60, 8, 19, 16 ]
复制代码

快速排序(quick sort)

根据中心点来拆分数组，把 <= 中心点的值放到中心点的左边，大于中心点的放在右边

问题抽象:

  function partition(A, lo, hi)
    A: 需要排序的数组
    lo: 开始位置(闭区间)
    hi: 结束位置(开区间)
    
    返回: 中心点所在位置
    副作用: [lo, hi]被中心点分成两个区域
  
  function qsort(A)
  A: 需要排序的数组
  返回: 无
复制代码

循环不变式:

  我们需要确定：
  <=中心点: [lo, i)
  未确定: [i, j)
  大于中心点: [j, hi)
  中心点: hi - 1
复制代码

程序实现:

  function partition(A, lo, hi) {
    const pivot = A[hi - 1]
    let i = lo, j = hi -1
    while(i !== j) {
     pivot >= A[i] ? i++ : swap(A, i, --j)
    }
    swap(A, j, hi - 1)
    return j
  }
  
  function swap(A, i, j) {
    [A[i], A[j]] = [A[j], A[i]]
  }
  
  function qsort(A, lo = 0, hi = A.length) {
    if (hi - lo < 2) return
    let pivot = partition(A, lo, hi)
    qsort(A, lo, pivot)
    qsort(A, pivot + 1, hi)
  }
  const A = [100, 2, 60, 19, 8, 16]
  qsort(A) // [ 2, 8, 16, 19, 60, 100 ]
复制代码

计数排序(counting sort)

遍历原数组，累计写入累计数组。然后加和累积数组，得到元素位置。

问题抽象:

  function counting_sort(A)
  A; 需要排序的数组
  返回: 结果数组
复制代码

程序实现:

  function counting_sort(A) {
    const max = Math.max(...A)
    // 累计数组
    const B = Array(max + 1).fill(0)
    // 结果数组
    const R = Array(A.length)
    // 累计数组递增
    A.forEach((_, i) => B[A[i]]++)
    // 累计求和
    for (let i = 1; i < B.length; i++) {
      B[i] += B[i-1]
    }
    for (const i of A.keys()) {
      const p = B[A[i]] - 1 // 回写位置
      B[A[i]]-- // 新回写位置
      R[p] = A[i] // 回写结果
    }
    return R
  }
  const A = [9, 2, 60, 19, 8, 16]
  console.log(counting_sort(A)) //[ 2, 8, 9, 16, 19, 60 ]
复制代码

基数排序(radix sort)

按照相同位有效数字的值分组排序整数。

问题抽象:

  function radix_sort(A) {
    for (let i of A中数字的位数()) {
      根据左边数第i位有效数字进行排序A
    }
  }
复制代码

程序实现:

  function radix_sort(A) {
    const max = Math.max(...A)
    const buckets = Array.from({ length: 10 }, () => [])
    // 有效数位
    let m = 1
    while(m < max) {
      // 将数组放入桶中
      A.forEach( num => {
        const digit = ~~ ( ( num % ( m * 10 )) / m )
        buckest[digit].push(num)
      })
      // 从桶中取出元素
      let j = 0
      buckets.forEach( bucket => {
        while(bucket.length > 0) {
          A[j++] = bucket.shift()
        }
      })
      // 下一个位置
      m *= 10
    }
  }
  const A = [9, 2, 600, 19, 8, 16]
  radix_sort(A  )
  console.log((A)) // [ 2, 8, 9, 16, 19, 600 ]
复制代码

桶排序(bucket sort)

计数排序是一种特殊的桶排序。

问题抽象:

  function bucket_sort(A, K, S)
  A: 需要排序的数组
  K: 桶的数量
  S: 每只桶的大小
  返回: 排序好的数组
复制代码

程序实现:

  function bucket_sort(A, K, S) {
    const buckets = Array.from({ length: K }, () => [])
    // 放入桶中
    for (let i of A.keys()) {
      const index = ~~(A[i] / S)
      buckets[index].push(A[i])
    }
    // 排序每只桶
    for (let i of buckets.keys()) {
      insertion_sort(buckets[i])
    }
    // 取出数据
    return [].concat(...buckets)
  }
  
  function insertion_sort(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
    }
  }
  const A = [9, 2, 600, 19, 80, 16]
  console.log(bucket_sort(A, 10, 100)) // [ 2, 9, 16, 19, 80, 600 ]
复制代码