🚧 经典排序算法

排序算法（Sorting algorithm）是一种能将一串元素依照特定排序方式进行排列的一种算法

0. 分类

本文章将算法按照稳定性进行分类。其中，稳定排序算法会让原本有相等键值的纪录维持相对次序。也就是如果一个排序算法是稳定的，当有两个相等键值的元素和，如果在之前，那么排序之后依然是在的前面。

1. 稳定的排序

冒泡排序-

冒泡排序（Bubble Sort）又称为泡式排序，是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

冒泡排序算法的运作如下：

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

图解：来源

/**
 * @author kotori y
 */

Array.prototype.bubbleSort = function () {

  for (let end = this.length - 2; end >= 1; end--) {
    let exchanged = false
    console.log(end)
    for (let start = 0; start <= end; start++) {
      if (this[start] > this[start + 1]) {
        [this[start], this[start + 1]] = [this[start + 1], this[start]];
        exchanged = true
      }
    }

    /* 如果没有交换证明排序已完成 */
    if (!exchanged) {
      return this
    }

  }
  return this
}


let num = [22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70];
num.bubbleSort()

console.log(num)

鸡尾酒排序-

鸡尾酒排序（cocktail sort），也就是定向冒泡排序，是冒泡排序的一种变形。此算法与冒泡排序的不同处在于排序时是以双向在序列中进行排序。

简单说就是左右横跳的冒泡排序

图解：来源

/**
 * @author Kotori Y
 */

Array.prototype.cocktailSort = function () {

  let leftPointer = 0, rightPointer = this.length - 1
  let exchanged = false

  while (leftPointer < rightPointer) {

    for (let i = leftPointer; i < rightPointer; i++) {
      if (this[i] > this[i+1]) {
        [this[i], this[i+1]] = [this[i+1], this[i]];
        exchanged = true
      }
    }
    if (!exchanged) {
      return this
    }
    rightPointer--
    exchanged = false

    for (let j = rightPointer; j > leftPointer; j--) {
      if (this[j] < this[j-1]) {
        [this[j], this[j-1]] = [this[j-1], this[j]];
        exchanged = true
      }
    }
    if (!exchanged) {
      return this
    }
    leftPointer++
    exchanged = false
  }

  return this
}


let num = [22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70];
num.cocktailSort()

console.log(num)

插入排序-

插入排序（Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

1. 从第一个元素开始，该元素可以认为已经被排序
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5. 将新元素插入到该位置后
6. 重复步骤2~5

图解：来源

/**
 * @author kotori y
 */

Array.prototype.insertionSort = function () {

  for (let i = 1; i < this.length; i++) {

    let currNum = this[i]
    let j = i - 1

    while (currNum < this[j] && j >= 0) {
      this[j + 1] = this[j]
      console.log(j)
      j--
    }
    this[j + 1] = currNum

  }
  
  return this
}

let num = [22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70];
num.insertionSort()

console.log(num)

计数排序-

计数排序（Counting sort）是一种稳定的线性时间排序算法。该算法于1954年由 Harold H. Seward 提出。计数排序使用一个额外的数组，其中第个元素是待排序数组中值等于的元素的个数。然后根据数组来将中的元素排到正确的位置。

算法的步骤如下：

1. 找出待排序的数组中最大和最小的元素
2. 统计数组中每个值为的元素出现的次数，存入数组的第项
3. 对所有的计数累加（从第一个元素开始，每一项和前一项相加）
4. 反向填充目标数组：将每个元素放在新数组的第项，每放一个元素就将减去1

图解：来源

/**
 * @author Kotori Y
 */

Array.prototype.countingSort = function () {

  let C = []

  for (let i = 0; i < this.length; i++) {
    C[this[i]] = (C[this[i]] || 0) + 1
  }

  let D = []

  for (let j = 0; j < C.length; j++) {
    if (C[j]) {
      const tmp = new Array(C[j]).fill(j)
      D.push(...tmp)
    }
  }

  return D
}

const arr = [11, 9, 6, 8, 1, 3, 5, 1, 1, 0, 100]
newArr = arr.countingSort()

console.log(newArr)

基数排序-

基数排序（Radix sort）是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数

算法的步骤如下：

1. 找出待排序的数组中最大的元素的位数（例如123是2，1234是4）；
2. 依次计算序列中每个元素第位的值，放到一个额外的数组中的第个数组中去；
3. 合并这个额外的数组作为新的待排序的数组；
4. 重复上述步骤，直至到达最大位数。

图解：来源

/**
 * @author Kotori Y
 */


Array.prototype.radixSort = function () {

  const maxNum = this.reduce((a, b) => a > b ? a : b)
  const maxBit = "".concat(maxNum).length

  for (let i = 1; i <= maxBit; i++) {
    let bucket = []
    for (let j = 0; j < this.length; j++) {
      const num = this[j]
      const bit = Math.floor((num % 10 ** i) / (10 ** (i - 1)))
      bucket[bit] = (bucket[bit] || []).concat(num)
    }
    this.splice(0)
    this.push(...bucket.reduce((a,b) => a.concat(b)))
  }

  return this
}


let num = [22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 614, 35, 9, 170];
num.radixSort()
console.log(num)

桶排序-

桶排序（Bucket sort）或所谓的箱排序，工作的原理是将数组分到有限数量的桶里。每个桶再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）

和计数排序和基数排序十分相似，均为线性的排序算法。大致流程为：

1. 设置一个定量的数组当作空桶子。
2. 寻访序列，并且把项目一个一个放到对应的桶子去。
3. 对每个不是空的桶子进行排序。
4. 从不是空的桶子里把项目再放回原来的序列中。

图解：来源

/**
 * @author Kotori Y
 */

Array.prototype.bucketSort = function (bucketSize = 6) {

  const bucket = []
  const maxNum = this.reduce((a, b) => a > b ? a : b),
    minNum = this.reduce((a, b) => a < b ? a : b)

  for (let i = 0; i < this.length; i++) {
    const interpolation = Math.floor(((this[i] - minNum) / (maxNum - minNum)) * (bucketSize - 1));
    bucket[interpolation] = (bucket[interpolation] || []).concat(this[i])
  }

  /* 递归 */
  for (let j = 0; j < bucketSize; j++) {
    if (bucket[j] && bucket[j].length > 1) {
      bucket[j].bucketSort()
    }
  }

  this.splice(0)
  this.push(...bucket.reduce((a, b) => a.concat(b)))
  return this
}


let num = [82, 32, 22, 34, 5, 64, 89, 50, 37, 3, 55, 35, 9, 70];
num.bucketSort()
console.log(num)

归并排序-

归并排序（Merge sort），是创建在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。

图解：来源

递归法（Top-down）

1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置
3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
4. 重复步骤3直到某一指针到达序列尾
5. 将另一序列剩下的所有元素直接复制到合并序列尾

/**
 * @author Kotori Y
 */

// 递归栈受浏览器的影响

const merge = (leftArr, rightArr) => {

  let ans = []
  while (leftArr.length && rightArr.length) {
    const tmpNum = leftArr[0] < rightArr[0] ? leftArr.shift() : rightArr.shift()
    ans.push(tmpNum)
  }
  return ans.concat(leftArr, rightArr)
}


Array.prototype.mergeSortTopDown = function () {

  if (this.length <= 1) return this
  const mid = (this.length / 2) | 0  // 取整操作
  let leftArr = this.slice(0, mid), rightArr = this.slice(mid)

  const res = merge(leftArr.mergeSortTopDown(), rightArr.mergeSortTopDown())
  this.splice(0)
  this.push(...res)
  return this
}

let num = [22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70];
num.mergeSortTopDown()
console.log(num)

迭代法（Bottom-up）

1. 将序列每相邻两个数字进行归并操作，形成个序列，排序后每个序列包含两/一个元素
2. 若此时序列数不是1个则将上述序列再次归并，形成个序列，每个序列包含四/三个元素
3. 重复步骤2，直到所有元素排序完毕，即序列数为1

/**
 * @author Kotori Y
 */


const merge = (leftArr, rightArr) => {

  let ans = []
  while (leftArr.length && rightArr.length) {
    const tmpNum = leftArr[0] < rightArr[0] ? leftArr.shift() : rightArr.shift()
    ans.push(tmpNum)
  }
  return ans.concat(leftArr, rightArr)
}


Array.prototype.mergeSortBottomUp = function () {

  for (let width = 1; width < this.length; width *= 2) {
    for (let i = 0; i < this.length; i += width * 2) {
      const tmp = merge(this.slice(i, i + width), this.slice(i + width, i + width * 2))
      this.splice(i, width * 2, ...tmp)
    }
  }

  return this
}


let num = [22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70];
num.mergeSortBottomUp()
console.log(num)

不稳定的排序

选择排序-

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

十分简单，唯一的优点可能就是空间复杂度是

/**
 * @author Kotori
 */

Array.prototype.selectSort = function () {


  for (let i = 0; i < this.length - 1; i++) {
    let tmp = i, minNum = this[i]
    for (let j = i + 1; j < this.length ; j++) {
      if (minNum > this[j]) {
        tmp = j
        minNum = this[j]
      }
    }
    [this[i], this[tmp]] = [this[tmp], this[i]];
  }

  return this
}


let num = [22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70];
num.selectSort()
console.log(num)