数组排序算法 — 冒泡排序

对于经典算法，你是否也遇到这样的情形：学时觉得很清楚，可过阵子就忘了？

本系列文章就尝试解决这个问题。

研读那些排序算法，细品它们的名字，其实都很贴切。

比如冒泡排序就很形象，遍历n次，每次循环相邻元素两两比较，把其中大的元素往后放。例如：

上图演示了冒泡过程的第一次循环。其中，最大的元素5就像气泡一样逐步上升到最后一位。

我们把上述过程直接翻译成代码：

let array = [5, 4, 3, 2, 1]
for (let i = 0; i < array.length - 1; i++) {
  if (array[i] > array[i+1]) {
    swap(array, i, i+1)
  }
}
console.log(array) // [4, 3, 2, 1, 5]
复制代码

其中swap函数封装了两个元素如何交换：

function swap(array, i, j) {
  [array[i], array[j]] = [array[j], array[i]]
}
复制代码

第一次遍历会把最大的元素放到倒数第一个位置上，第二次遍历会把第2大的元素放倒数第二个位置上。

其余次数，以此类推。此时，我们也很容易把这n次遍历写出来：

for (let j = 0; j < array.length; j++) {
  for (let i = 0; i < array.length - 1; i++) {
    if (array[i] > array[i+1]) {
      swap(array, i, i+1)
    }
  }
}
复制代码

上述代码，还有优化的空间，比如第2次遍历时，元素4和5其实是不需要再比较的。因为上一次已经把未排好序中最大的数据挑走了。查看完整代码：

const utils = {
  swap(array, i, j) {
    [array[i], array[j]] = [array[j], array[i]]
  },
  randomNum() {
    return Math.floor(Math.random() * 100)
  },
  randomArray() {
    return Array.from(Array(this.randomNum()), _ => this.randomNum())
  }
}

function bubbleSort(array) {
  const length = array.length
  for (let i = 0; i < length; i++) {
    for (let j = 0; j < length -1 - i; j++) {
      if (array[j] > array[j + 1]) {
        utils.swap(array, j, j + 1)
      }
    }
  }
  return array
}
const array = bubbleSort(utils.randomArray())

console.log(array)

至此，冒泡排序原理和实现已经说完了。

这里总结一下，冒泡排序不需要额外空间，是本地排序，相等元素是不会交换前后顺序，因而也是稳定排序，时间复杂度为O(n^2)，适用于少量数据排序，但实际中用得不多。

参考链接：
https://juejin.im/post/5d6dcd59e51d45620c1c5416