各位老铁，从本节开始，我们进入排序算法的世界。

对于前端来说，排序算法在应用方面似乎始终不是什么瓶颈——JS 天生地提供了对排序能力的支持，很多时候，我们实现排序只需要这样寥寥数行的代码：

arr.sort((a,b) => {
    return a - b
})

以某一个排序算法为“引子”，顺藤摸瓜式地盘问，可以问出非常多的东西，这也是排序算法始终热门的一个重要原因——面试官可以通过这种方式在较短的时间里试探出候选人算法能力的扎实程度和知识链路的完整性。因此排序算法在面试中的权重不容小觑。

以面试为导向来看，需要大家着重掌握的排序算法，主要是以下5种：

基础排序算法：

• 冒泡排序
• 插入排序
• 选择排序
• 进阶排序算法
• 归并排序
• 快速排序

我们的学习安排就按照这个从基础到进阶的次序来。

和以往不同的是，本专题的讲解线索不再是“题目”，而是排序算法本身：针对每一种算法，我都会首先介绍其思想，然后为大家逐步示范一遍真实的排序过程，接着为大家做编码教学。最后，别忘了，排序算法的时间复杂度也是一个不能忽视的考点，“编码复盘”部分我们不见不散。

注意：考虑到排序类题目在未经特别声明的情况下，都默认以“从小到大排列”为有序标准。因此下文中所有”有序“的描述指代的都是“从小到大排列”。

冒泡排序

⚡ 30 秒速记

• 相邻两个比，前面大就交换，每一轮把剩下的最大值「冒」到右边
• 第 i 轮结束，右边 i 个元素已经在最终位置
• 加 swapped 标记：一轮没交换就提前结束，有序输入最好 O(n)
• 平均、最坏 O(n²)，原地 O(1)；只在严格 > 时交换才稳定
• 生产代码别手写冒泡，直接用 Array.prototype.sort，从 ES2019 起规范要求它稳定

冒泡排序就是相邻两个数比大小，前面大就换，一轮下来最大的数会被一路推到最右边，像气泡浮上来一样。 所以每过一轮，右边就多一个排好的元素，下一轮不用再管它。我写的时候会加一个 swapped 标记，一整轮都没交换说明已经有序，直接退出，这样有序输入只要 O(n)。平均和最坏还是 O(n²)，空间 O(1)，比较用严格大于就能保证稳定。

function bubbleSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let swapped = false
    for (let j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) { // 用 > 不用 >=，相等不换才稳定
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
        swapped = true
      }
    }
    if (!swapped) break
  }
  return arr
}
bubbleSort([5, 3, 2, 4, 1]) // [1, 2, 3, 4, 5]