前端开发必会的JS算法之冒泡排序

很多做前端开发的小伙伴都有这样的情况，对于 JS 的一些经典算法，在学时都觉得很清楚，当时也确实学会了，小手啪啪不在话下，然后过一阵子就会遗忘了，再让他动手写就显得很生疏，甚至哪儿学的还到哪儿去。所以，本系列文章就尝试解决这个问题。

比如冒泡排序就很形象，遍历 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)，适用于少量数据排序，但实际中用得不多。

冒泡排序，要做到能分分钟手写出来，是需要掌握其排序原理的。每次遍历核心是相邻两两比较，一旦内层遍历能写出来，那么整体就很容易写出来，不需要死记硬背的。

以上就是前端开发必会的 JS 算法之冒泡排序的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，同时也希望多多支持码云笔记！