Sorting algorithms

排序算法简介

欢迎！在本章中，我们将一起探讨排序算法 (Sorting Algorithms)。简单来说，排序就是将项目按特定顺序排列的过程，例如字母顺序 (A-Z) 或数字顺序 (1-10)。

为什么这很重要呢？试想一下，如果电话簿里的姓名不是按字母顺序排列，找一个人会多困难！电脑需要对数据进行排序，以便之后能更快速地搜索。我们将专注于 AQA 考试中最重要的两种方法：冒泡排序法 (Bubble Sort) 和 归并排序法 (Merge Sort)。

1. 冒泡排序法 (Bubble Sort)

冒泡排序法是最容易理解的排序算法之一。它的名称由来是因为较大的数值会像汽水中的气泡一样，逐步“浮”到列表的末端！

运行原理（机制）

该算法通过不断地扫描列表来运行。以下是详细步骤：

1. 检查列表中的前两个项目。
2. 如果顺序错误，就将它们交换 (Swap)；如果顺序正确，则保持不动。
3. 移动到下一对项目（第 2 和第 3 个项目），并重复比较。
4. 持续进行直到抵达列表末端。这个过程称为一轮 (Pass)。
5. 算法会重复进行这些轮次，直到某次完整的轮次中完全没有进行任何交换。这就是它判断列表已排序完成的方法！

现实生活中的例子

想象有四名学生排成一列，你想根据身高（由矮到高）对他们进行排序：[Dave (180cm), Alice (155cm), Chris (170cm), Bob (160cm)]。

第一轮：
- 比较 Dave 和 Alice。Dave 较高，所以交换。[Alice, Dave, Chris, Bob]
- 比较 Dave 和 Chris。Dave 较高，所以交换。[Alice, Chris, Dave, Bob]
- 比较 Dave 和 Bob。Dave 较高，所以交换。[Alice, Chris, Bob, Dave]
Dave 已经“冒泡”到最后了！

第二轮：
- 比较 Alice 和 Chris。顺序正确，无需交换。
- 比较 Chris 和 Bob。Chris 较高，所以交换。[Alice, Bob, Chris, Dave]
- 比较 Chris 和 Dave。顺序正确，无需交换。

第三轮：
- 比较 Alice 和 Bob。顺序正确，无需交换。
- 比较 Bob 和 Chris。顺序正确，无需交换。
- 比较 Chris 和 Dave。顺序正确，无需交换。
第三轮没有进行任何交换，列表排序完成！

快速复习：冒泡排序法

- 动作： 比较相邻的项目并进行交换。
- 停止条件： 当完整的一轮中没有任何交换时。
- 最适用于： 非常小的列表，或是几乎已经排好序的列表。

常见错误： 学生常以为算法在跑完一轮后就会停止。记住，通常需要多轮 (Multiple passes) 才能将每个项目放到正确的位置！

关键点： 冒泡排序法易于理解和编写，但对于大量数据来说，速度通常很慢。

2. 归并排序法 (Merge Sort)

归并排序法对于大型列表来说，是一种快得多的算法。它使用了一种称为分治法 (Divide and Conquer) 的技术。它不是逐个交换项目，而是将列表拆分成微小的碎片，然后再按正确顺序重新组装。

运行原理（机制）

如果起初觉得有点复杂，别担心！它主要分为两个阶段：

第一阶段：分割 (Divide)
算法会不断将列表对半分，直到每个项目都成为独立的微小列表（只有一个项目的列表，技术上来说已经是排序好的了！）。

第二阶段：征服/归并 (Conquer/Merge)
算法开始将这些微小的列表重新归并。每次归并两个列表时，它都会将项目按正确顺序排列。它会持续进行此过程，直到只剩一个完整且已排序的列表为止。

视觉类比

想象一副乱掉的纸牌。你把牌堆分成两份，然后是四份、八份，直到你手上拿着单张牌为止。然后，你取出两张牌并排好顺序，接着将这两对归并成一个已排序的四张牌组，依此类推。

你知道吗？ 对于像社交媒体网站上所有用户列表这样庞大的数据集，归并排序法比冒泡排序法有效率得多。

快速复习：归并排序法

- 动作： 重复将列表对半分，然后按顺序归并回来。
- 技术： 分治法 (Divide and Conquer)。
- 最适用于： 大型数据列表。

关键点： 归并排序法在大型列表中比冒泡排序法更快，但编程较困难，且因为必须建立许多子列表，会消耗更多电脑内存。

3. 比较这两种算法

在考试中，你可能会被问到为何选择某种算法而非另一种。以下是一个简单的对比，帮助你做决定。

冒泡排序法

优点：
- 写法和理解起来非常简单。
- 不需要额外太多内存（它在“原地/In place”进行排序）。

缺点：
- 对于大型列表来说效率低（速度慢）。

归并排序法

优点：
- 即使处理海量列表也非常有效率（速度快）。
- 无论原始列表有多乱，其运行时间都相当稳定。

缺点：
- 编程较为复杂。
- 使用更多内存，因为过程中需要建立许多子列表。

记忆小撇步： 把 Bubble 看作 "Basic"（基本，简单但慢），把 Merge 看作 "Modern"（现代，复杂但快）。

快速复习：效率

当我们谈论这些算法的“效率”时，通常是指时间效率 (Time Efficiency)，即电脑完成任务所需的时间。随着列表长度增加，冒泡排序法完成任务所需的时间增加速度，远比归并排序法快得多。

关键点： 对于只有 5 个项目的短列表，冒泡排序法完全没问题。但对于 500 万个项目的列表，你必须使用归并排序法！

总结检查清单

你能够做到以下几点吗？

- [ ] 解释冒泡排序法如何利用轮次 (passes) 和交换 (swaps)？
- [ ] 描述归并排序法中使用的“分治法”？
- [ ] 说出冒泡排序法的一个优点？（易于编写/占用内存较少）
- [ ] 说出归并排序法的一个优点？（大型列表处理速度较快）