用 JavaScript 动手敲一敲经典排序算法

做前端一直没怎么接触算法之类，看到一篇文章 - 十大经典排序算法总结（JavaScript描述）

学习过程中动手敲一敲其中的示例，接下来记录一下用 js 实现经典排序算法的过程。

冒泡排序（Bubble Sort）

冒泡排序，我的理解就是循环判断当前的数字和下一个数字的大小，如果当前大于下一个，则把当前的放到后面。这样子，排序完成后最后一个就是最大的数字。就像是气泡从水底冒上来一样。

const array = [10, 2, 23, 123, 12, 32, 34, 56, 1, 98, 11, 22, 33, 298, 4]

function sort (array) {
  let result = [...[], ...array]
  let count = 0

  for (let i = 0; i < result.length; i++) {
    for (let j = 0; j < result.length; j++) {
      if (result[j] > result[j + 1]) {
        const currentNumber = result[j]
        const nextNumber = result[j + 1]

        result[j] = nextNumber
        result[j + 1] = currentNumber
      }
      count++
    }
  }

  console.log('count', count) // 225
  console.log(result) // [ 1, 2, 4, 10, 11, 12, 22, 23, 32, 33, 34, 56, 98, 123, 298 ]
}

sort(array)

冒泡排序最坏情况的时间复杂度是 （n²）。那么，优化一下。试想一下，冒泡排序时是从第一个开始，到最后一个。那经历一次循环后，最后一个肯定是最大的数。下一次排序则没必要比较最后一个，以此类推。接下来，改进的过程中，记录下最后一次比较的位置，下一次比较这个位置后面的就不去比较了。

const array = [10, 2, 23, 123, 12, 32, 34, 56, 1, 98, 11, 22, 33, 298, 4]

function sort (array) {
  let result = [...[], ...array]
  let lastExchangePosition = result.length
  let exchangePosition = 0
  let count = 0

  for (let i = 0; i < result.length; i++) {
    for (let j = 0; j < lastExchangePosition; j++) {
      if (result[j] > result[j + 1]) {
        const currentNumber = result[j]
        const nextNumber = result[j + 1]

        result[j] = nextNumber
        result[j + 1] = currentNumber

        exchangePosition = j
      }
      count++
    }
    lastExchangePosition = exchangePosition
  }

  console.log('count', count) // 109
  console.log(result) // [ 1, 2, 4, 10, 11, 12, 22, 23, 32, 33, 34, 56, 98, 123, 298 ]
}

sort(array)

优化前的时间复杂度是15²=225，优化后的时间复杂度为123，少了一半。

选择排序（Selection Sort）

选择排序的原理是，从头开始循环去找最小或者最大的数，找到后与数组首位数交换。下一次则从下一个数字开始去查找最小的数，再次交换。其时间复杂度是(n-1)！。

const array = [10, 2, 23, 123, 12, 32, 34, 56, 1, 98, 11, 22, 33, 298, 4]

function sort (array) {
  let result = [...[], ...array]
  let count = 0
  let minNumberIndex = 0

  for (let i = 0; i < result.length; i++) {
    minNumberIndex = i

    for (let j = i + 1; j < result.length; j++) {
      minNumberIndex = result[j] < result[minNumberIndex] ? j : minNumberIndex
      count++
    }

    const minNumber = result[minNumberIndex]
    const currentNumber = result[i]

    result[minNumberIndex] = currentNumber
    result[i] = minNumber
  }

  console.log('count', count) //  ( 15 - 1 )! = 105
  console.log(result) // [ 1, 2, 4, 10, 11, 12, 22, 23, 32, 33, 34, 56, 98, 123, 298 ]
}

sort(array)

插入排序（Insertion Sort）

插入排序简单的应用场景就是打扑克牌，从第二张牌开始，向前面的牌去一一比较，找到插入的位置后将其插入。

const array = [10, 2, 23, 123, 12, 32, 34, 56, 1, 98, 11, 22, 33, 298, 4]

function sort (array) {
  let result = [...[], ...array]
  let count = 0

  for (let i = 1; i < result.length; i++) {
    const current = result[i]
    let j = i - 1

    while (current < result[j] && j >= 0) {
      result[j + 1] = result[j]
      j--
      count++
    }
    result[j + 1] = current
  }

  console.log('count', count) // 44
  console.log(result) // [ 1, 2, 4, 10, 11, 12, 22, 23, 32, 33, 34, 56, 98, 123, 298 ]
}

sort(array)