Sorting algorithms

排序算法简介

欢迎！在本章中，我们将探讨计算机科学中最基础的任务之一：排序 (Sorting)。无论你是在 Amazon 上筛选最便宜的商品，还是浏览社交媒体上朋友的最新贴文，幕后都有排序算法在处理这些数据，确保它们以正确的顺序呈现。

对于 AQA A Level 课程，你需要掌握两种特定的算法：冒泡排序 (Bubble Sort) 和 归并排序 (Merge Sort)。我们将研究它们的运作方式、如何一步步进行演算，以及它们的效率如何。如果起初觉得有些抽象也不用担心，我们会使用大量的现实生活比喻，让你轻松掌握！

预备概念：请记住，数组 (Array) 其实就是一个项目的列表。排序的过程就是将这些项目（通常是数字）重新排列为升序（从小到大）。

1. 冒泡排序 (Bubble Sort)

冒泡排序通常是学生学习的第一种排序算法。它以简单易懂著称，但正如你之后会看到的，对于大量数据来说，它的速度并不快！

运作方式：“上升气泡”比喻

想象汽水里的一串气泡。更大、更“重”的气泡会浮到上面。在冒泡排序中，算法会遍历列表，比较相邻的项目，如果顺序错误就将它们交换 (Swap)。这个过程会不断重复，直到最大的数字像“气泡”一样浮到列表的最末端。

步骤拆解

1. 从列表的最开头开始。
2. 比较前两个项目。
3. 如果第一个项目大于第二个，就进行交换。
4. 移动到下一对项目并重复此步骤，直到列表结束（这称为一轮扫描/Pass）。
5. 对整个列表重复上述过程，直到某次扫描过程中完全没有发生任何交换为止。

让我们试着演练一次！

假设我们有这个列表：[5, 1, 4]

第一轮扫描 (Pass 1)：
• 比较 5 和 1。5 比 1 大，进行交换。列表变为：[1, 5, 4]
• 比较 5 和 4。5 比 4 大，进行交换。列表变为：[1, 4, 5]
数字 5 现在已经“浮”到了最后面！

第二轮扫描 (Pass 2)：
• 比较 1 和 4。1 较小，不交换。
• 比较 4 和 5。4 较小，不交换。
这一轮没有进行任何交换，所以列表已经排序完成！

效率与复杂度

冒泡排序被认为是一种效率极低的算法。如果你有一个包含 \(n\) 个项目的列表，你可能需要将每个项目与其他所有项目进行比较。

• 时间复杂度： \(O(n^2)\)（多项式时间）。
• 为什么？ 因为它使用了嵌套循环 (Nested loops)——一个循环用来遍历列表，另一个循环则持续重复进行扫描。

快速复习：
• 最适用于：非常小的列表，或是已经几乎排好序的列表。
• 常见错误：以为扫描一次列表就排序完成了。你必须持续进行扫描，直到完全没有发生交换为止！

关键要点：冒泡排序简单但速度慢。其时间复杂度为 \(O(n^2)\)。

2. 归并排序 (Merge Sort)

对于大型列表，归并排序比冒泡排序快得多。它使用了一种聪明的策略，称为分治法 (Divide and Conquer)。

运作方式：“扑克牌”比喻

想象你有一堆杂乱的 100 张扑克牌。要一次把它们全排好很难。但如果你把它们分成两堆各 50 张，再分成四堆各 25 张，一直分下去直到剩下 100 堆各只有 1 张牌……嗯，只有 1 张牌的那一堆已经算“排好序”了！然后，你只需要小心地将这些堆按正确顺序合并 (Merge) 回来即可。

分治阶段

阶段 1：拆分 (Divide)

算法不断将列表一分为二，直到每个子列表只剩下一个元素。根据定义，只有一个元素的列表本身就是排好序的。

阶段 2：合并 (Conquer/Merge)

随后，算法将这些子列表合并回来。在合并过程中，它会比较每个子列表前端的项目，并将较小的一个先放入新的组合列表中。

演练归并排序

列表：[8, 3, 5, 1]

步骤 1 (拆分)： 分成 [8, 3] 和 [5, 1]。
步骤 2 (拆分)： 分成 [8], [3], [5], [1]。
步骤 3 (合并)： 将 [8] 和 [3] 合并为 [3, 8]。将 [5] 和 [1] 合并为 [1, 5]。
步骤 4 (合并)： 合并 [3, 8] 和 [1, 5]。比较 3 和 1（1 较小），然后比较 3 和 5（3 较小），接着比较 8 和 5（5 较小），最后剩下 8。结果：[1, 3, 5, 8]。

效率与复杂度

由于归并排序每次都会将列表对半分割，它的效率远高于冒泡排序。

• 时间复杂度： \(O(n \log n)\)。
• 为什么？ 「\(\log n\)」来自于我们能将列表对半分割的次数，而「\(n\)」则来自于将项目合并回来所需的处理工作。

你知道吗？ 归并排序比冒泡排序需要更多的内存（空间复杂度），因为在过程中必须建立新的子列表！

关键要点：归并排序是一种“分治”算法，时间复杂度为 \(O(n \log n)\)。

总结比较表

冒泡排序
• 方法：交换相邻项目。
• 复杂度： \(O(n^2)\)。
• 效能：慢，处理大量数据时效率低下。

归并排序
• 方法：分治法 (Divide and Conquer)。
• 复杂度： \(O(n \log n)\)。
• 效能：快，处理大量数据时效率高。

快速复习：检查你的理解

• 哪一种算法是“分治法”的例子？（答案：归并排序）
• 冒泡排序的时间复杂度是多少？（答案： \(O(n^2)\)）
• 为什么冒泡排序被认为效率低下？（答案：它需要多次扫描和比较，特别是当列表变大时。）
• 如果你有一个包含 100 万用户的庞大数据库，你应该使用哪种排序？（答案：归并排序，因为对于较大的 \(n\) 值， \(O(n \log n)\) 比 \(O(n^2)\) 快得多。）

如果觉得演练归并排序的过程有点“递归”或绕口也不用担心！只要记住核心概念：拆分到只剩单个，然后依序缝合起来。