Sorting algorithms

欢迎来到排序的世界！

在本章中，我们将探讨计算机如何将杂乱的数据整理成井然有序的列表。无论是按姓名排序通讯录，还是按歌手排序音乐库，排序算法（Sorting Algorithms）都是幕后的功臣。我们将专注于课程大纲要求的两种特定方法：冒泡排序法（Bubble Sort）和归并排序法（Merge Sort）。别担心这些术语听起来很生硬——看完这些笔记后，你就能像专业人士一样轻松处理它们了！

1. 冒泡排序法 (Bubble Sort)

冒泡排序法通常是学生学习的第一种排序算法。它非常易于理解，但正如你稍后会看到的，它并不是完成任务最高效的方法！

运作原理：类比说明

想象一排身高不同的学生，你想按从矮到高将他们排列。你从左边开始，比较前两名学生；如果左边的学生比右边的高，就让他们交换位置。你对每一对学生重复这个动作，直到最高的学生像“气泡”一样浮动到队伍的最末端。然后，你再从头开始重复整个过程。

逐步逻辑

1. 从列表的开端开始。
2. 比较前两个项目。
3. 如果第一个项目大于第二个，就交换它们。
4. 移动到下一对并重复此步骤，直到到达列表末端（这称为一轮（Pass））。
5. 对整个列表重复上述过程，直到无需再进行任何交换为止。

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

标准的冒泡排序法可能非常慢。课程要求你掌握两种使其更高效的方法：

• 缩小搜索范围：第一轮结束后，最大的项目必定已到达末端。第二轮后，最大的两个项目都已到位。因此，每一轮过后，我们检查的项目数量都可以减少一个。
• 使用“交换标记（Swapped flag）”：如果我们进行完整的一轮后没有发生任何交换，这意味着列表已经排序完成！我们可以使用不定次数迭代（Indefinite iteration）（例如 While 循环）来提早结束算法。

应避免的常见错误

“差一错误（Off-by-One Error）”：编写冒泡排序代码时要记住，如果列表有 \(n\) 个项目，你只需要比较 \(n-1\) 对。如果你尝试将最后一个项目与其“右边”的某个东西进行比较，程序就会崩溃，因为右边根本没有项目！

快速回顾：冒泡排序法编写简单，但对于大量数据而言效率低下。它在处理“已接近排序”的列表时表现最好。

2. 归并排序法 (Merge Sort)

如果说冒泡排序法是一个缓慢的“冒泡”过程，那么归并排序法则使用了一种更聪明的策略，称为分治法（Divide and Conquer）。

运作原理：类比说明

想象你有一副凌乱的扑克牌。与其一次排序整副牌，不如将它分成两半。接着再将这两半继续对半分，直到变成 52 张单独的牌。由于单张牌本身就是“已排序”的，你就可以开始按正确顺序将它们归并（Merging）回来。

两个阶段

1. 分割阶段（Divide Phase）：将列表反复对分，直到每个子列表只剩下一个项目为止。
2. 归并阶段（Merge Phase）：将子列表重新归并。归并两个列表时，计算机会比较两者的第一个项目，并将较小的一个放入新的归并列表中。重复此步骤，直到最后剩下一份完全排序好的列表。

归并排序演示

假设我们有列表 [8, 3, 5, 1]：
• 分割： [8, 3] 和 [5, 1]
• 再次分割： [8], [3], [5], [1]
• 归并（第一轮）： [3, 8] 和 [1, 5]
• 归并（第二轮）： 比较 3 和 1（1 较小），然后比较 3 和 5（3 较小），然后比较 8 和 5（5 较小），最后剩下 8。结果为：[1, 3, 5, 8]。

重点提示：你不需要在 AS Level 考试中编写归并排序的代码，但你必须能够通过图表或跟踪表（Trace table）展示其分割和归并数据的过程。

3. 算法比较

在考试中，你可能会被问到为何选择其中一种算法。以下是详细分析：

时间效率

• 冒泡排序法：对于大型列表非常慢。其效能很大程度上取决于起始顺序。如果列表已排序，优化后的冒泡排序速度非常快；但如果是反序，那简直是一场灾难！
• 归并排序法：对于大型列表快得多。它的效能非常稳定，无论列表是已排序还是完全随机，所需的时间大约相同。

内存（空间）效率

• 冒泡排序法：对内存非常友好！它在“原地（In-place）”进行排序，意味着不需要建立数据的额外副本。
• 归并排序法：会占用更多内存，因为它在“分割”阶段必须建立许多小的子列表。

“你知道吗？”

归并排序法由现代计算机架构之父之一约翰·冯·诺依曼（John von Neumann）于 1945 年发明。至今，它仍然是专业软件中最流行的排序方法之一！

4. 总结表

算法：冒泡排序法 (Bubble Sort)
适用场景：小型列表或已接近排序的数据。
主要优点：编写简单；内存占用极少。
主要缺点：对于大型、未排序的数据集非常慢。

算法：归并排序法 (Merge Sort)
适用场景：对速度有要求的数据集。
主要优点：速度快且效能稳定。
主要缺点：需要更多内存来存储子列表。

记忆法：S 规则

• Bubble（气泡）很 Basic（基础），但对于大数据来说很 Bad（糟糕）。
• Merge（归并）很 Modern（现代），而且速度 Much（快得多）。

成功的小秘诀：跟踪冒泡排序法时，请务必画底线标示你当前正在比较的对象。跟踪归并排序法时，画出分割与归并的“树状”结构——这能让你更清楚地掌握数字的移动路径，不容易出错！