第 3.4.2 章：排序算法——化繁为简

你好！欢迎来到排序算法的世界。在这里，我们将学习计算机是如何将杂乱无章的数据整理成整齐、可用的列表的。试想一下，如果图书馆里的书没有任何顺序，寻找某一本特定的书简直就是一场灾难！通过对数据进行排序，我们可以让搜索任务（你在上一节中学到的内容！）变得极其高效。

在本章中，我们将深入研究两种主要的排序算法：简单但缓慢的冒泡排序 (Bubble Sort)，以及强大且快速的归并排序 (Merge Sort)。你需要准确掌握它们的工作原理、如何进行分步追踪，以及它们在效率上的对比。让我们开始吧！


1. 冒泡排序算法 (Bubble Sort)

冒泡排序可能是最容易理解的排序算法，但它也是效率最低的算法之一。它的工作原理是反复遍历列表，比较相邻的元素，如果它们的顺序错误，就交换它们的位置。

1.1 冒泡排序的工作原理：类比

想象一下水中有一串气泡，每一个代表一个数字。较大的气泡上升得更快。冒泡排序的原理正是如此：在每一轮遍历中，剩余未排序元素中最大的那个会像气泡一样“浮”到列表的末尾。

1.2 分步追踪（基础版）

冒泡排序包含对数据进行多次遍历 (Passes)。在每一轮遍历中，我们使用循环来迭代所有的相邻对。

让我们追踪列表：[5, 1, 4, 2]

第一轮 (Pass 1)

  • 比较 5 和 1。(5 > 1)。交换。列表变为：[1, 5, 4, 2]

  • 比较 5 和 4。(5 > 4)。交换。列表变为：[1, 4, 5, 2]

  • 比较 5 和 2。(5 > 2)。交换。列表变为：[1, 4, 2, 5]

    最大元素 (5) 现在已正确放置在末尾。

第二轮 (Pass 2)

  • 比较 1 和 4。(1 不大于 4)。无需交换。列表变为：[1, 4, 2, 5]

  • 比较 4 和 2。(4 > 2)。交换。列表变为：[1, 2, 4, 5]

  • 比较 4 和 5。(我们只需要检查到倒数第二个项目，因为最后一个项目 (5) 已经排好序了。但在基础版本中，我们可能会继续检查。)

    第二大元素 (4) 现在已正确放置。

第三轮 (Pass 3)

  • 比较 1 和 2。无需交换。列表：[1, 2, 4, 5]

  • 比较 2 和 4。无需交换。列表：[1, 2, 4, 5]

由于在第三轮中没有进行任何交换，说明列表已经排好序，算法可以停止（如果我们使用的是优化版本，详见下文）。

快速回顾：冒泡排序过程

冒泡排序使用迭代 (Iteration)（循环）反复比较相邻元素，如果顺序不对就进行交换，直到列表完全排好序为止。

1.3 提升冒泡排序的效率（优化）

标准实现使用的是确定性迭代 (Definite iteration)（固定的遍历次数）。然而，我们可以通过两个关键改进使其更高效：

  1. 减少检查次数： 在每一轮完整的遍历后，未排序项中最大的那个元素总是会归位到最终的正确位置。因此，在下一轮遍历中，我们可以将待检查的元素数量减一。

  2. 提前终止（不确定性迭代）： 如果完成了一轮完整的遍历且没有任何交换发生，则说明列表已经完全排好序了。我们可以使用一个布尔标志（例如 swapped = False），并将总循环从确定性迭代改为不确定性迭代 (Indefinite iteration)（例如，只要发生了交换就继续执行的 WHILE 循环）。这使得排序过程能够在某轮遍历中未发生任何交换时立即停止。

你知道吗？ 冒泡排序算法的时间效率很大程度上取决于列表初始时的排序程度。如果列表已经是部分排序的，高效版本（带有提前终止功能）将更快结束！

冒泡排序的关键点： 代码编写非常简单（你可能会被要求编写其代码！），但它很慢，特别是当列表很大且非常杂乱时。它的主要优势在于，如果数据已经基本排好序，它利用优化手段可以非常快速地完成排序。


2. 归并排序算法 (Merge Sort)

归并排序是一种比冒泡排序快得多且更先进的排序算法。它是分治法 (Divide and Conquer) 技术的典型代表。

2.1 归并排序的工作原理：分治法

归并排序主要分为两个阶段：

  1. 分 (Divide)： 不断地将列表对半分，直到拥有许多只包含一个元素的小列表。根据定义，只有一个元素的列表本身就是排好序的。

  2. 治 (Conquer/Merge)： 将这些小列表以有序的方式反复合并在一起，直到只剩下一个排好序的完整列表。

类比：想象你要整理一堆巨大的文件夹。与其挨个比较，不如把这一叠文件夹分成两小叠，交给朋友，请他们分别整理各自那一半。当他们把整理好的半叠拿回来时，你只需要快速地将这两个已经有序的半叠合并成一叠大的有序文件夹即可。

2.2 分步演示（追踪）

让我们演示归并排序如何处理列表：[8, 3, 1, 6, 9, 2]

第一阶段：拆分 (Divide)

我们递归地将列表减半，直到只剩下单个元素。

  • 开始：[8, 3, 1, 6, 9, 2]

  • 拆分 1：[8, 3, 1] | [6, 9, 2]

  • 拆分 2：[8] | [3, 1] | [6] | [9, 2]

  • 拆分 3（达到基准情况）：[8] | [3] | [1] | [6] | [9] | [2]

第二阶段：合并 (Conquer)

我们合并相邻的单元素列表，确保结果列表是有序的。

  • 合并 1：[3, 8]（合并 [8] 和 [3]）| [1, 6]（合并 [1] 和 [6]）| [2, 9]（合并 [9] 和 [2]）

  • 合并 2：[1, 3, 6, 8]（合并 [3, 8] 和 [1, 6]）| [2, 9]

  • 合并 3（最终合并）：[1, 2, 3, 6, 8, 9]（合并 [1, 3, 6, 8] 和 [2, 9]）

注意：归并排序最关键的部分是合并操作本身。你需要比较两个已排序子列表的第一个元素，反复选取较小的一个放入新的合并列表中。

归并排序的关键点： 归并排序通过高效地划分问题保证了快速的排序时间。你只需要能够解释或演示它如何处理一组数据即可；考试中不会要求你编写其代码。


3. 排序算法效率对比

当我们比较算法时，会从时间和内存使用两个维度考察它们的效率。

3.1 时间效率 (速度)

时间效率衡量的是随着输入数据大小（通常记为 n）的增加，执行时间如何增长。我们使用 大 O 表示法 (Big O notation) 来正式比较增长率（A-Level 考试要求）。

  • 冒泡排序：

    • 最坏情况时间复杂度： \(O(n^2)\)。这很慢。如果你将列表大小增加一倍 (n)，所需时间将增加为原来的四倍 (\(n^2\))。

    • 最好情况时间复杂度： \(O(n)\)。如果列表已经是排好序的（并且我们使用了优化），它只需要一轮与 n 成正比的遍历来检查一切。

  • 归并排序：

    • 最坏情况时间复杂度： \(O(n \log n)\)。这非常快。对于大型数据集，它的扩展性远好于 \(O(n^2)\)。

    • 最好情况时间复杂度： \(O(n \log n)\)。无论列表是否已经排好序，归并排序所花费的时间大致相同。

时间结论： 对于大型、未排序的数据集，归并排序通常远快于冒泡排序，因为 \(O(n \log n)\) 的增长率优于 \(O(n^2)\)。

记忆小贴士：为什么归并排序更快？

冒泡排序浪费时间去反复比较那些已经检查过的元素对，特别是在元素需要从列表前端移到末尾时。归并排序通过仅合并那些已知已排序的列表来避免了这种情况。

3.2 空间效率 (内存使用)

空间效率衡量的是算法除了输入列表本身外，还需要多少额外内存。

  • 冒泡排序： 几乎不需要额外的内存（只需少量变量用于追踪交换和指针）。它是原地排序 (In-place sort)。

  • 归并排序： 需要与输入列表大小成正比的额外内存 (\(O(n)\))，因为它在合并过程中需要临时存储空间来存放子列表。

内存结论： 在内存使用（空间维度）方面，冒泡排序比归并排序更高效，因为归并排序在合并步骤中需要大量的临时空间。


对比总结表

（冒泡排序与归并排序的效率对比）

特性： 时间效率（最坏情况）

冒泡排序： $O(n^2)$ (慢)

归并排序： $O(n \log n)$ (快)

特性： 对初始排序顺序的依赖

冒泡排序： 是。如果部分有序，它会更快结束（最好情况 $O(n)$）。

归并排序： 否。无论如何都花费 $O(n \log n)$。

特性： 空间效率

冒泡排序： 极佳（原地排序，内存使用极低）。

归并排序： 较差（合并时需要 $O(n)$ 的额外内存）。

最终总结： 如果你面对的是巨大的数据集且速度至关重要，请使用归并排序。如果你内存极其有限，或者预期数据大部分已经排好序，那么（优化后的）冒泡排序可能是更好的选择。