排序算法对比：冒泡排序、归并排序与快速排序

排序算法会把同一组元素重新排列成有序状态，比如从小到大。如果先说结论：冒泡排序很简单，但对大列表通常太慢；归并排序能稳定提供 $O(n \log n)$ 的性能；快速排序在划分比较均衡时，实际运行往往很快。

真正该问的不是“哪种排序最好”，而是“在什么条件下最好”。冒泡排序适合理解局部交换，归并排序能清楚展示分治思想，而快速排序则说明了为什么即使没有最坏情况保证，平均性能依然可能很强。

排序算法做什么

给定一个列表，比如 $[5, 1, 4, 2]$，算法应该返回按顺序排列后的相同元素：

$$[1, 2, 4, 5]$$

这听起来很简单，但不同算法达到这个结果的方式差别很大。主要区别在于：

• 它们如何移动元素
• 它们通常需要多少次比较或交换
• 它们需要多少额外内存
• 它们对不良输入模式有多敏感

冒泡排序：反复交换相邻元素

冒泡排序会遍历列表，并交换顺序错误的相邻元素。完整扫描一轮后，当前未排序部分中最大的元素就会“冒泡”到末尾。

对 $[5, 1, 4, 2]$ 来说，第一轮是这样的：

$$[5, 1, 4, 2] \to [1, 5, 4, 2] \to [1, 4, 5, 2] \to [1, 4, 2, 5]$$

然后它会在剩余未排序部分继续重复，直到不再需要交换。

冒泡排序主要用于学习。一般来说，它的时间复杂度是 $O(n^2)$，所以随着列表变大，比较次数会迅速增加。对于课堂上的小例子，这没有问题；但对于真正的排序任务，它通常不是合适的选择。

归并排序：先拆分，再排序，最后合并

归并排序使用的是分治思想。它先把列表拆成更小的部分，对这些部分分别排序，再把排好序的部分合并起来。

对于 $[5, 1, 4, 2]$，一种清晰的表示方式是：

$$[5, 1, 4, 2] \to [5, 1] + [4, 2]$$

分别排好每一半：

$$[5, 1] \to [1, 5], \qquad [4, 2] \to [2, 4]$$

然后合并这两个有序部分：

$$[1, 5] + [2, 4] \to [1, 2, 4, 5]$$

归并排序最大的优点是可预测性。按通常分析，它的运行时间是 $O(n \log n)$，而不只是平均情况下如此。它的主要代价是内存：常见的基于数组的实现，在合并时需要额外空间。

快速排序：围绕基准值进行划分

快速排序也使用分治思想，但方式不同。它会选一个基准值，把较小的元素放到一边、较大的元素放到另一边，然后递归地对两边继续排序。

在 $[5, 1, 4, 2]$ 中，如果选基准值 $4$，一种可能的划分是：

$$[1, 2] \;|\; 4 \;|\; [5]$$

这样左右两部分都小得多，所以后续排序会很快完成。

快速排序在实际中通常很快，因为很多实现会原地划分，并且当基准值能把列表分得比较均衡时，问题规模会迅速缩小。但这个条件很重要。如果基准值反复选得不好，比如一次又一次地分出一个很小的部分和一个几乎完整的部分，那么最坏情况就会变成 $O(n^2)$。

冒泡排序 vs 归并排序 vs 快速排序

算法	核心思想	典型时间	最坏情况时间	额外内存
冒泡排序	反复交换相邻元素	$O(n^2)$	$O(n^2)$	低
归并排序	拆分、排序各半、再合并	$O(n \log n)$	$O(n \log n)$	在常见数组实现中较高
快速排序	围绕基准值划分	通常为 $O(n \log n)$	$O(n^2)$	通常低于归并排序

如果你只想记住一个实用结论，那就是：冒泡排序是教学型算法，归并排序是稳定且可预测的选择，而快速排序在实现能妥善处理基准值时，往往是实际中更快的选择。

在同一个列表上看一个完整例子

使用同一个列表：

$$[5, 1, 4, 2]$$

冒泡排序会不断修正局部错误。它并不会“看到”整体结构，所以可能需要很多轮。

归并排序先把问题拆成更小的有序部分，再把它们组合起来。这种结构就是它在列表变大时仍能保持稳定性能的原因。

快速排序则尝试尽早做出一次有效划分。如果划分足够均衡，后面的工作量就会迅速减少。

这也是为什么学生在看过同一个列表经过这三种方法的变化后，往往更容易记住复杂度数字。那些数字并不是随意贴上的标签，它们反映的是算法如何减少无序。

比较排序算法时的常见错误

认为快速排序总是更快

快速排序在实际中通常很快，但并不保证在所有情况下都是最快的。糟糕的基准值选择会严重拖慢它。

把所有 $O(n \log n)$ 算法都当成一样

归并排序和快速排序可能有相同的平均增长率，但它们在内存使用、最坏情况保证和实现细节上并不相同。

因为冒泡排序容易写就使用它

代码容易写，不等于适合实际使用。做很小的演示时，冒泡排序没问题；但面对更大的真实输入时，它通常会做很多不必要的工作。

忽略输入模型

这些比较通常假设的是：对一般输入进行基于比较的排序。如果数据具有特殊结构，那么像计数排序这样的非比较排序，可能会彻底改变选择结果。

各种排序算法在什么情况下使用

冒泡排序主要用于教学、手动跟踪过程，以及那些清晰性比性能更重要的极小规模示例。

归并排序适用于需要稳定的 $O(n \log n)$ 表现，并且可以接受额外内存开销的场景。根据具体实现，它也很适合链表，以及那些需要稳定排序的情况。

快速排序适用于重视实际运行速度，并且实现中有良好基准值策略或回退保护机制的场景。许多标准库的排序策略会结合快速排序的思想和保护措施，而不是直接使用朴素的教材版本。

快速记住它们区别的方法

按“动作”来记：

• 冒泡排序修正相邻元素
• 归并排序构造有序的两半
• 快速排序围绕基准值拆分

这种心智图像比死记三个名字和三个公式更有用。

试着自己做一版

拿列表 $[7, 3, 6, 1]$，分别跟踪一轮冒泡排序、一次归并排序的拆分与合并过程，以及一次快速排序的基准值划分。如果你能解释为什么这个列表在三种情况下变化方式不同，那就说明你真正理解了这个概念。