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

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

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

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

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

基础排序算法：

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

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

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

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

冒泡排序

⚡ 30 秒速记

• 相邻逆序就交换，每轮把未排序区最大值送到右端。
• 一轮没有交换可提前结束：最好 O(n)，平均/最坏 O(n²)。
• 只在严格 > 时交换可保持稳定；原地空间 O(1)。
• 第 i 轮后，右侧 i 个元素已经最终归位。

冒泡排序会反复比较相邻元素，发现逆序就交换，每一轮把未排序区间的最大值推到最右侧。 因此第 i 轮结束后，右边已有 i 个元素处在最终位置，不必再参与比较。我一般会加一个 swapped 标记，一轮没有交换就提前结束，使已有序输入达到 O(n)。平均和最坏时间仍是 O(n²)，原地空间为 O(1)，只在严格大于时交换还能保持稳定。

回答参考：“冒泡维护的是右侧已排好区间。每轮扫描相邻对，把最大值逐步推到边界；我会加 swapped 标记优化已有序输入。”

💬 面试官追问

• 订单列表页按金额冒泡排序时，两条金额相同的记录交换了先后位置；如果比较条件写的是 >=，这和页面要求的稳定顺序有什么冲突？

  使用 >= 会交换相等元素，使它们原有的相对次序被改变，因此不能保证稳定性。若页面依赖后端原顺序作为隐含次级排序，应只在左项严格大于右项时交换；否则即使金额有序，用户仍会看到同价订单跳动。

• 后台管理页偶尔接收已经有序的数组，你会怎样在现有冒泡实现中避免继续跑完所有轮次？

  每轮开始将 swapped 置为 false，发生相邻交换时改为 true；一轮结束仍为 false，说明当前扫描范围已无逆序相邻对，可以直接终止。该优化只改善已有序或较接近有序的输入，不能改变冒泡排序在一般大规模数据上的局限。

• 需求从几十条教学样例变成前端一次处理大量记录，负责人仍要求沿用冒泡排序以减少改动，你会怎样评估？

  不应仅因代码现成就默认沿用，因为冒泡需要反复扫描并比较相邻项，数据规模增大时通常不适合作为生产排序方案。应优先确认是否可使用运行环境提供的排序能力或调整数据处理位置；若必须保留冒泡，至少限制输入规模并避免阻塞交互线程。

• 线上反馈逆序数组排序后末尾仍有一个较大值错位，但已排序数组看不出异常；你会先检查哪个循环边界？

  先检查每轮是否完整扫描到当前未排序区间的最后一对相邻元素，以及右侧已排序边界是否缩减过早。冒泡依赖每轮把本轮最大值推到边界，漏掉一次 arr[i] 与 arr[i+1] 的比较就无法建立该性质；逆序输入最容易暴露这种偏一错误。

• 评审者提出记录“本轮最后一次交换位置”来缩短下一轮扫描，与单纯 swapped 标记相比值得采用吗？

  两者解决的层次不同：swapped 用于识别整轮无交换并提前结束，最后交换位置还能缩小下一轮的未排序边界。若实现清晰且有近乎有序输入，可以组合使用；若数据很小或教学目标强调基本过程，额外状态可能增加边界错误而收益有限。