# 算法（Edexcel IAL 数学 D1）

> Edexcel 国际A-Level 数学 · IAL D1
> 来源: https://www.owlsprep.com/zh/study/edexcel-ial-math-d1-algorithms/

本指南涵盖Edexcel IAL 决策数学1（D1）的所有核心算法内容，包括流程图、排序算法、装箱方法和二分查找，完全符合2018年IAS考纲要求。

**先修:** 基础数值排序; 理解有序列表和无序列表的概念

## 学习目标

- 定义算法并能从文本或流程图中实现算法
- 在快速排序和二分查找中应用中间项规则选择基准元素
- 执行冒泡排序、快速排序、首次适应算法、降序首次适应算法和满箱装箱
- 在有序列表中正确执行二分查找

## 1. 算法基础与中间项规则

算法是完成任务的有限分步指令序列。你需要能够实现以文本或流程图形式给出的算法，并在排序和查找算法中应用中间项规则选择基准元素。

**中间项规则** — 对于包含N个元素的列表，查找中间项的位置：若N为奇数，位置为$\lceil\frac{1}{2}(N+1)\rceil$。若N为偶数，位置为$\frac{1}{2}(N+2)$。

*例:* 对于6个元素的列表：N=6为偶数，位置为第4项。对于5个元素的列表：N=5为奇数，位置为第3项。

**例题:** 分别计算N=7和N=8的列表中中间项的位置。

1. N=7（奇数）：代入奇数N的公式

   $$\left\lceil \frac{7+1}{2} \right\rceil = 4$$
2. N=7的列表中间项位于第4位
3. N=8（偶数）：代入偶数N的公式

   $$\frac{8+2}{2} = 5$$
4. N=8的列表中间项位于第5位

> **考试提示:** 在从列表中选取基准元素值之前，务必先写出中间项的位置，避免因基准选择错误丢失分数。

*计算器:* allowed

## 2. 冒泡排序算法

冒泡排序通过反复遍历列表，比较相邻元素对，若顺序错误则交换，直到列表排序完成。你必须在作答中展示每一次遍历和每一次交换，才能获得全部分数。

**冒泡排序** — 排序算法，比较相邻元素，交换顺序错误的元素对，重复操作直到完整遍历过程中没有发生任何交换。

*例:* 将[3,1,4,2]按升序排序需要3次完整遍历。

**例题:** 使用冒泡排序将列表[7, 2, 9, 1, 5]按升序排序，展示所有遍历过程。

1. 第1次遍历：比较相邻元素，顺序错误则交换：7↔2交换，7和9不交换，9↔1交换，9↔5交换 → 第1次遍历结束：[2,7,1,5,9]（最后1个元素已排序）
2. 第2次遍历：检查前4个元素：2和7不交换，7↔1交换，7↔5交换 → 第2次遍历结束：[2,1,5,7,9]（最后2个元素已排序）
3. 第3次遍历：检查前3个元素：2↔1交换，2和5不交换 → 第3次遍历结束：[1,2,5,7,9]（最后3个元素已排序）
4. 第4次遍历：检查前2个元素：1和2不交换，本次遍历无任何交换 → 列表排序完成
5. 最终排序列表：[1,2,5,7,9]

> **考试提示:** 每次遍历后，下一个最大的未排序元素会“冒泡”到它的正确位置，因此你可以每次将遍历的比较次数减少1，以节省时间。

*计算器:* allowed

## 3. 快速排序算法（中间项基准）

快速排序是分治排序算法，使用基准元素将列表拆分为小于基准和大于基准的子列表，然后递归排序每个子列表。你必须对每个子列表都使用中间项规则选择基准元素。

**快速排序** — 分治排序算法，选择基准元素，重排列表使小于基准的元素在左侧，大于基准的元素在右侧，然后对每个子列表重复操作直到所有元素排序完成。

*例:* 对于包含4个元素的子列表，根据中间项规则选择第3个元素作为基准。

**例题:** 使用快速排序将列表[6, 3, 8, 1, 9, 2]按升序排序，使用中间项规则选择基准元素。

1. 原始列表N=6为偶数：基准位置为第4项=1。拆分：小于1的元素=[]，基准=[1]，大于1的元素=[6,3,8,9,2]
2. 排序右侧子列表[6,3,8,9,2]，N=5为奇数：基准位置为第3项=8。拆分：小于8的元素=[6,3,2]，基准=[8]，大于8的元素=[9]
3. 排序[6,3,2]，N=3为奇数：基准位置为第2项=3。拆分：小于3的元素=[2]，基准=[3]，大于3的元素=[6]
4. 合并所有已排序部分：[] + [1] + [2,3,6] + [8] + [9] = [1,2,3,6,8,9]

> **考试提示:** 即使你能立刻看出最终排序列表，也要清晰标注每个基准元素并展示所有子列表拆分过程，才能获得全部步骤分。

*计算器:* allowed

## 4. 装箱算法

装箱算法的目标是将给定大小的物品装入数量最少的固定容量箱子。你需要掌握三种方法：首次适应、降序首次适应和满箱装箱。

**装箱方法** — 1. 首次适应：按给定顺序将每个物品放入第一个能容纳它的箱子。2. 降序首次适应：先将物品按降序排序，再应用首次适应规则。3. 满箱装箱：先组合物品装满尽可能多的满箱，剩余物品再用首次适应装箱。

*例:* 满箱装箱可以在可行时得到最优（最小）箱子数量，而首次适应是一种近似启发式算法。

**例题:** 将大小为6、3、5、7、2、4的物品装入容量为10的箱子，分别使用(a)首次适应、(b)降序首次适应、(c)满箱装箱完成。

1. (a) 首次适应：按给定顺序处理物品。结果：箱1(6,3)，箱2(5,2)，箱3(7)，箱4(4) → 共使用4个箱子
2. (b) 降序首次适应：先将物品降序排序：[7,6,5,4,3,2]。应用首次适应：箱1(7,3)，箱2(6,4)，箱3(5,2) → 共使用3个箱子
3. (c) 满箱装箱：先找出满箱组合：7+3=10，6+4=10。剩余物品5、2放入箱3 → 共使用3个箱子

> **考试提示:** 对于降序首次适应，要明确展示排序后的物品列表；对于满箱装箱，要展示所有满箱组合，才能获得全部分数。

*计算器:* allowed

## 5. 二分查找算法

二分查找仅用于在**有序**列表中查找目标元素，通过反复将目标与当前子列表的中间项比较，每次排除一半的列表，直到找到目标或确认目标不存在。

**二分查找** — 适用于有序列表的高效查找算法，每次使用中间项排除一半的搜索空间，直到定位目标或确认目标不存在。

**例题:** 使用二分查找在有序列表[1,2,4,5,7,9,10,12]中查找目标值10，展示所有步骤。

1. 原始列表N=8为偶数：中间位置为第5项=7。10>7，排除左半部分，搜索右侧子列表[9,10,12]
2. 子列表N=3为奇数：中间位置为第2项=10。中间项等于目标，在原始列表的第7位找到目标

> **考试提示:** 二分查找仅适用于预先排序的列表。如果给定无序列表，必须先排序再应用二分查找，并且要明确说明你执行了排序操作。

*计算器:* allowed

## 常见错误

- **错误做法:** 使用错误的中间项位置公式（例如对偶数N使用N/2）
  - 原因: Edexcel 明确要求使用指定的中间项规则，错误的基准选择会导致你丢失快速排序和二分查找的所有步骤分。
  - 正确做法: 牢记：奇数N → $\lceil\frac{1}{2}(N+1)\rceil$，偶数N → $\frac{1}{2}(N+2)$。在选择基准元素值之前先写出位置。
- **错误做法:** 在冒泡排序中跳过遍历或交换步骤，仅展示最终排序列表
  - 原因: 分数是为每一次正确的中间遍历设置的，即使最终列表正确，缺失步骤也会导致丢失步骤分。
  - 正确做法: 写出每次遍历中的每一次比较和交换，并且清晰标注每一次遍历。
- **错误做法:** 执行降序首次适应装箱时，不对物品排序就直接使用首次适应
  - 原因: 降序首次适应要求先将物品按降序排序，跳过这一步意味着你使用了错误的方法。
  - 正确做法: 在对降序首次适应方法应用首次适应之前，务必明确将物品排序为降序，并展示排序后的列表。
- **错误做法:** 对无序列表应用二分查找
  - 原因: 二分查找仅适用于排序列表，对无序数据使用会得到错误结果，并且不会获得任何分数。
  - 正确做法: 首先检查列表是否有序；如果无序，先排序再开始二分查找，并且说明这一步骤。
- **错误做法:** 假设首次适应装箱能得到最优箱子数量
  - 原因: 首次适应是启发式算法，不是最优算法，因此它使用的箱子数量通常会多于必要值。
  - 正确做法: 说明满箱装箱可以在可行时得到最优解，首次适应/降序首次适应是近似方法。

## 速查表

| 算法 | 核心步骤 | 考试要求 |
| --- | --- | --- |
| 中间项规则 | 奇数N: $\lceil\frac{1}{2}(N+1)\rceil$，偶数N: $\frac{1}{2}(N+2)$ | 选择数值之前先计算位置 |
| 冒泡排序 | 比较相邻元素对，交换顺序错误的元素，重复直到无交换 | 展示每一次遍历和所有交换 |
| 快速排序 | 选择中间基准，拆分为小于基准/大于基准的子列表，重复操作 | 标注所有基准和子列表拆分 |
| 首次适应装箱 | 将每个物品放入第一个能容纳它的可用箱子 | 按给定顺序处理物品 |
| 降序首次适应装箱 | 将物品降序排序，再应用首次适应 | 先展示排序后的物品列表 |
| 满箱装箱 | 先装满尽可能多的满箱，剩余物品用首次适应装箱 | 展示所有满箱组合 |
| 二分查找 | 将目标与有序列表的中间项比较，排除一半，重复操作 | 仅在有序列表上使用，展示所有比较 |

## 下一步

掌握D1核心算法后，你就可以进入Edexcel IAL 决策数学1的下一个基础主题：图与网络。通过练习历年真题中的算法题目提升速度和准确率，算法题占D1 IAS试卷分值的15%左右。请务必展示每一步的完整过程，因为Edexcel 的大部分分数都给到步骤而非最终答案。你还需要练习解读算法流程图，这是一种直接基于本部分内容的常见考试题型。

---

来自 [OwlsPrep](https://www.owlsprep.com) —— A-Level / IB / AP / IGCSE 免费学习指南，依据官方考纲编写。原页面：https://www.owlsprep.com/zh/study/edexcel-ial-math-d1-algorithms/