算法（Edexcel IAL 数学 D1）
Edexcel 国际A-Level 数学· WDM11 2018 Specification Issue 3· 25 分钟阅读
1. 1. 算法基础与中间项规则★★☆☆☆⏱ 5 min
✓ 计算器
算法是完成任务的有限分步指令序列。你需要能够实现以文本或流程图形式给出的算法，并在排序和查找算法中应用中间项规则选择基准元素。
中间项规则
对于包含N个元素的列表，查找中间项的位置：若N为奇数，位置为。若N为偶数，位置为。
例:
对于6个元素的列表：N=6为偶数，位置为第4项。对于5个元素的列表：N=5为奇数，位置为第3项。
分别计算N=7和N=8的列表中中间项的位置。
- 1
N=7（奇数）：代入奇数N的公式
- 2
N=7的列表中间项位于第4位
- 3
N=8（偶数）：代入偶数N的公式
- 4
N=8的列表中间项位于第5位
Exam tip:
在从列表中选取基准元素值之前，务必先写出中间项的位置，避免因基准选择错误丢失分数。
2. 2. 冒泡排序算法★★☆☆☆⏱ 5 min
✓ 计算器
冒泡排序通过反复遍历列表，比较相邻元素对，若顺序错误则交换，直到列表排序完成。你必须在作答中展示每一次遍历和每一次交换，才能获得全部分数。
冒泡排序
排序算法，比较相邻元素，交换顺序错误的元素对，重复操作直到完整遍历过程中没有发生任何交换。
例:
将[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]
Exam tip:
每次遍历后，下一个最大的未排序元素会“冒泡”到它的正确位置，因此你可以每次将遍历的比较次数减少1，以节省时间。
3. 3. 快速排序算法（中间项基准）★★★☆☆⏱ 5 min
✓ 计算器
快速排序是分治排序算法，使用基准元素将列表拆分为小于基准和大于基准的子列表，然后递归排序每个子列表。你必须对每个子列表都使用中间项规则选择基准元素。
快速排序
分治排序算法，选择基准元素，重排列表使小于基准的元素在左侧，大于基准的元素在右侧，然后对每个子列表重复操作直到所有元素排序完成。
例:
对于包含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]
Exam tip:
即使你能立刻看出最终排序列表，也要清晰标注每个基准元素并展示所有子列表拆分过程，才能获得全部步骤分。
4. 4. 装箱算法★★★☆☆⏱ 5 min
✓ 计算器
装箱算法的目标是将给定大小的物品装入数量最少的固定容量箱子。你需要掌握三种方法：首次适应、降序首次适应和满箱装箱。
装箱方法
- 首次适应：按给定顺序将每个物品放入第一个能容纳它的箱子。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个箱子
Exam tip:
对于降序首次适应，要明确展示排序后的物品列表；对于满箱装箱，要展示所有满箱组合，才能获得全部分数。
5. 5. 二分查找算法★★☆☆☆⏱ 3 min
✓ 计算器
二分查找仅用于在有序列表中查找目标元素，通过反复将目标与当前子列表的中间项比较，每次排除一半的列表，直到找到目标或确认目标不存在。
二分查找
适用于有序列表的高效查找算法，每次使用中间项排除一半的搜索空间，直到定位目标或确认目标不存在。
使用二分查找在有序列表[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位找到目标
Exam tip:
二分查找仅适用于预先排序的列表。如果给定无序列表，必须先排序再应用二分查找，并且要明确说明你执行了排序操作。
6. 常见陷阱
错误做法:
使用错误的中间项位置公式（例如对偶数N使用N/2）
原因:
Edexcel 明确要求使用指定的中间项规则，错误的基准选择会导致你丢失快速排序和二分查找的所有步骤分。
正确做法:
牢记：奇数N → ，偶数N → 。在选择基准元素值之前先写出位置。
错误做法:
在冒泡排序中跳过遍历或交换步骤，仅展示最终排序列表
原因:
分数是为每一次正确的中间遍历设置的，即使最终列表正确，缺失步骤也会导致丢失步骤分。
正确做法:
写出每次遍历中的每一次比较和交换，并且清晰标注每一次遍历。
错误做法:
执行降序首次适应装箱时，不对物品排序就直接使用首次适应
原因:
降序首次适应要求先将物品按降序排序，跳过这一步意味着你使用了错误的方法。
正确做法:
在对降序首次适应方法应用首次适应之前，务必明确将物品排序为降序，并展示排序后的列表。
错误做法:
对无序列表应用二分查找
原因:
二分查找仅适用于排序列表，对无序数据使用会得到错误结果，并且不会获得任何分数。
正确做法:
首先检查列表是否有序；如果无序，先排序再开始二分查找，并且说明这一步骤。
错误做法:
假设首次适应装箱能得到最优箱子数量
原因:
首次适应是启发式算法，不是最优算法，因此它使用的箱子数量通常会多于必要值。
正确做法:
说明满箱装箱可以在可行时得到最优解，首次适应/降序首次适应是近似方法。
7. 速查表
算法 | 核心步骤 | 考试要求 |
|---|---|---|
中间项规则 | 奇数N: ，偶数N: | 选择数值之前先计算位置 |
冒泡排序 | 比较相邻元素对，交换顺序错误的元素，重复直到无交换 | 展示每一次遍历和所有交换 |
快速排序 | 选择中间基准，拆分为小于基准/大于基准的子列表，重复操作 | 标注所有基准和子列表拆分 |
首次适应装箱 | 将每个物品放入第一个能容纳它的可用箱子 | 按给定顺序处理物品 |
降序首次适应装箱 | 将物品降序排序，再应用首次适应 | 先展示排序后的物品列表 |
满箱装箱 | 先装满尽可能多的满箱，剩余物品用首次适应装箱 | 展示所有满箱组合 |
二分查找 | 将目标与有序列表的中间项比较，排除一半，重复操作 | 仅在有序列表上使用，展示所有比较 |
8. 常见问题
我需要展示排序算法的每一步吗？
是的，Edexcel 会为每一次正确的遍历/比较打分，因此你必须清晰写出每一个中间步骤，即使你立刻知道最终的排序列表。
快速排序应该使用哪个基准元素规则？
你必须使用中间项规则：对于包含N个元素的列表，若N为奇数，位置为，若N为偶数，位置为。在选择基准元素值之前，务必先说明其位置。
深入阅读
下一步
掌握D1核心算法后，你就可以进入Edexcel IAL 决策数学1的下一个基础主题：图与网络。通过练习历年真题中的算法题目提升速度和准确率，算法题占D1 IAS试卷分值的15%左右。请务必展示每一步的完整过程，因为Edexcel 的大部分分数都给到步骤而非最终答案。你还需要练习解读算法流程图，这是一种直接基于本部分内容的常见考试题型。