欢迎来到排序算法的世界！
在本章中，我们将学习电脑是如何将数据进行排序的。无论是游戏中的高分列表、手机里的通讯录，还是购物网站上的商品，电脑都是通过排序算法来整理信息的。如果起初觉得这听起来很「数学」，别担心——它其实就像整理一副凌乱的纸牌一样简单！
我们将重点探讨 AQA GCSE 考试中最重要的两种算法：冒泡排序法 (Bubble Sort) 和 合并排序法 (Merge Sort)。
1. 冒泡排序法 (Bubble Sort)
冒泡排序法通常是学生学习的第一个算法，因为它非常直观。它的运作原理是将列表中的最大值像气泡一样，一个接一个地「浮」到列表的末端。
运作流程：逐步解析
假设我们有一个数字列表：[5, 2, 4, 1]
步骤 1：比较前两个数字（5 和 2）。因为 5 大于 2，所以我们将它们交换 (swap)。
列表现在变为：[2, 5, 4, 1]
步骤 2：比较下一组（5 和 4）。因为 5 大于 4，所以我们将它们交换。
列表现在变为：[2, 4, 5, 1]
步骤 3：比较最后一组（5 和 1）。因为 5 大于 1，所以我们将它们交换。
列表现在变为：[2, 4, 1, 5]
你有发现吗？数字 5 已经像气泡一样「浮」到了列表末端的正确位置！这就是第一轮遍历 (pass) 的结束。现在，算法会从头开始重复这个过程，直到不再需要任何交换为止。
记忆小撇步：碳酸饮料
想象一下气泡饮料。最大的「气泡」（最大的数字）会最先浮到顶部（列表的末端）！
快速回顾：冒泡排序法的机制
• 它会比较相邻 (adjacent) 的项目（彼此相邻的项目）。
• 如果它们顺序错误，就进行交换。
• 它需要对列表进行多次遍历。
• 当某一次遍历过程中完全没有进行任何交换时，排序即告完成。
重点总结：冒泡排序法容易理解且几乎不需要额外的内存空间，但在处理长列表时速度会非常慢。
2. 合并排序法 (Merge Sort)
合并排序法就聪明多了。它被称为分治法 (Divide and Conquer) 算法。它不是一个一个地交换项目，而是先将列表拆分成极小的片段，然后再按正确顺序将它们组装回来。
运作流程：两个主要阶段
阶段 1：分割 (Divide)
算法会不断将列表对半分，直到每个项目都变成独立的微小列表。例如，[5, 2, 4, 1] 会变成 [5]、[2]、[4] 和 [1]。
阶段 2：征服与合并 (Conquer/Merge)
现在，它开始将这些微小列表重新合并。每次合并两个列表时，它都会将数字按正确顺序排列：
1. [5] 和 [2] 合并变成 [2, 5]
2. [4] 和 [1] 合并变成 [1, 4]
3. 最后，将 [2, 5] 和 [1, 4] 合并成 [1, 2, 4, 5]
现实生活的类比：整理衣物
想象你有成堆的袜子。如果你试图一次过整理整堆袜子，会很混乱。但如果你将大堆袜子分成小堆，先整理好小堆，最后再将它们拼在一起，速度就会快得多！
你知道吗？
合并排序法是递归 (recursive) 的。这意味着算法会调用自身的版本，来处理在「分割」阶段产生的较小次列表！
重点总结：对于大量数据，合并排序法比冒泡排序法快得多；但它比较复杂，且因为需要建立新的次列表，会占用较多的内存。
3. 比较：冒泡排序法 vs. 合并排序法
在考试中，你可能会被要求比较这两种方法。以下是它们优缺点的简单分析。
冒泡排序法
优点：
1. 编写和理解起来非常简单。
2. 几乎不需要额外内存（它是「原地」排序）。
缺点：
1. 对于长列表非常缺乏效率且缓慢。
2. 因为必须多次重复扫描同一列表，所以耗时较长。
合并排序法
优点：
1. 对于大型列表，速度快且效率更高。
2. 运行时间稳定（无论初始列表有多混乱，表现都很一致）。
缺点：
1. 程序编写较为复杂。
2. 使用更多内存，因为需要储存所有较小的次列表。
常见错误陷阱
学生常认为冒泡排序法比较好，因为它比较简单。千万别掉入这个陷阱！在计算机科学中，「更好」通常代表「处理大数据的时间复杂度更低」。而在这场竞赛中，合并排序法每次都胜出。
重点总结：在列表非常小或内存极度受限的情况下，请使用冒泡排序法。除此之外，特别是在处理大型数据库时，请使用合并排序法！
快速检查：哪个是哪个？
如果在考题中看到这些关键字，你就知道它们在谈论哪个算法了：
• 「相邻项目」(Adjacent items) 或 「交换」(Swapping) → 冒泡排序法
• 「分治法」(Divide and Conquer) 或 「分割与合并」(Splitting and Merging) → 合并排序法
你一定做得到的！排序只不过是电脑为了厘清混乱所遵循的一套规则。继续练习这些逐步的交换与分割，你很快就会成为排序专家！