📚 A-Level Maths: Algorithm Essentials | A-Level 数学：算法 考点精讲
Algorithms form the backbone of decision mathematics in A-Level Maths. Mastering common algorithms—from sorting and searching to critical path analysis and linear programming—is essential for exam success. This guide breaks down each algorithm with step-by-step explanations and practical examples.
算法是 A-Level 数学决策模块的核心。掌握从排序搜索到关键路径分析与线性规划的常见算法，是考试成功的关键。本指南通过逐步解析和实例，逐一拆解每个算法。
1. What is an Algorithm? | 什么是算法？
An algorithm is a finite sequence of well-defined, unambiguous instructions designed to solve a specific problem. Every algorithm must have an input, produce an output, be deterministic (same steps produce the same outcome), and terminate after a finite number of steps.
算法是一系列定义明确、无歧义的指令，用于解决特定问题，且步骤有限。每个算法必须有输入、产生输出、具备确定性（相同步骤产生相同结果），并在有限步后终止。
In decision mathematics, algorithms are often expressed using pseudocode or flowcharts. They are evaluated on efficiency, measured by the number of comparisons or steps, and on whether they produce an optimal solution or just a ‘good enough’ solution (heuristic).
在决策数学中，算法常用伪代码或流程图表达。算法的效率通过比较次数或步骤数衡量，也考察其能否得出最优解，抑或仅是一个“足够好”的解（启发式算法）。
2. Pseudocode and Flowcharts | 伪代码与流程图
Pseudocode is a simplified, language-independent way of describing the logic of an algorithm using common programming constructs such as IF…THEN…ELSE, FOR loops, and WHILE loops. Indentation is used to show nesting.
伪代码是一种简化的、与编程语言无关的描述算法逻辑的方式，使用 IF…THEN…ELSE、FOR 循环和 WHILE 循环等常见结构，用缩进表示嵌套。
Flowcharts use standard symbols: ovals for start/end, rectangles for processes, diamonds for decisions, and arrows for flow direction. They give a visual representation that helps trace an algorithm step by step.
流程图使用标准符号：椭圆表示开始/结束，矩形表示处理步骤，菱形表示判断，箭头表示流向。流程图提供了一种可视化的方式，便于逐步追踪算法。
3. Bubble Sort Algorithm | 冒泡排序算法
Bubble Sort repeatedly steps through a list, compares adjacent items, and swaps them if they are in the wrong order. The largest element “bubbles” to the end in each pass. The algorithm stops when a pass occurs with no swaps.
冒泡排序反复遍历列表，比较相邻元素，若顺序错误则交换。每遍历一次，最大的元素便“冒泡”到末尾。当某次遍历未发生交换时，算法结束。
Example: Sort [5, 3, 8, 2, 7] into ascending order.
示例：将列表 [5, 3, 8, 2, 7] 按升序排列。
| Pass | List after pass | Swaps? |
| 1 | [3, 5, 2, 7, 8] | Yes |
| 2 | [3, 2, 5, 7, 8] | Yes |
| 3 | [2, 3, 5, 7, 8] | Yes |
| 4 | [2, 3, 5, 7, 8] | No → stop |
The number of passes is at most n−1 for a list of size n. Bubble sort is simple but inefficient for large lists with O(n²) comparisons in the worst case.
对于长度为 n 的列表，遍历次数最多为 n−1。冒泡排序简单，但对于大列表效率低下，最坏情况需 O(n²) 次比较。
4. Quick Sort Algorithm | 快速排序算法
Quick Sort selects a pivot (often the middle item) and partitions the list into two sublists: elements less than the pivot and elements greater than the pivot. It then recursively sorts the sublists. The pivot stays in its final position after partitioning.
快速排序选取一个轴值（通常为中间项），将列表划分为两个子列表：小于轴值的元素和大于轴值的元素。然后递归地对子列表排序。划分后轴值即处于其最终位置。
Example: Sort [7, 2, 9, 4, 3, 8] using the middle element as pivot.
示例：使用中间元素为轴值对 [7, 2, 9, 4, 3, 8] 排序。
Select pivot = 9. Sublist left: [7,2,4,3,8], right: []. After placing pivot: [7,2,4,3,8] 9 2,3], right = [7,8]. Continue until all sublists size 1. Final sorted list: [2,3,4,7,8,9].
选择轴值 9。左子列表：[7,2,4,3,8]，右子列表：[]。放置轴值后：[7,2,4,3,8] 9 []。接着排序左子列表：轴值 4，左 = [2,3]，右 = [7,8]。继续直到所有子列表长度为 1。最终排序列表：[2,3,4,7,8,9]。
Quick sort is efficient with an average complexity of O(n log n), but the choice of pivot can affect performance.
快速排序平均复杂度为 O(n log n)，效率较高，但轴值的选择会影响性能。
5. Binary Search Algorithm | 二分查找算法
Binary search locates a target value within a sorted list by repeatedly dividing the search interval in half. Compare the target with the middle element; if not equal, eliminate half the list and continue.
二分查找通过反复将搜索区间减半，在已排序列表中定位目标值。将目标与中间元素比较；若不相等，则舍弃一半列表后继续。
Example: Find 23 in [2, 5, 8, 12, 16, 23, 38, 45, 50].
示例：在 [2, 5, 8, 12, 16, 23, 38, 45, 50] 中查找 23。
| Step | Low | High | Mid (value) | Action |
| 1 | 1 | 9 | 5 → 16 | 23 > 16, set Low=6 |
| 2 | 6 | 9 | 7 or 8? Use floor( (6+9)/2 )=7 → 38 | 23 < 38, set High=6 |
| 3 | 6 | 6 | 6 → 23 | Found |
Binary search runs in O(log n) time and is much faster than linear search on large sorted lists.
二分查找的时间复杂度为 O(log n)，在大型有序列表上远比线性查找快。
6. First-Fit and First-Fit Decreasing Bin Packing | 首次适应与递减首次适应装箱算法
Bin packing algorithms aim to pack items of given sizes into bins of fixed capacity, minimising the number of bins used. The First-Fit (FF) algorithm places each item into the first bin that has enough remaining capacity.
装箱算法旨在将给定大小的物品装入固定容量的箱子中，并最小化所用箱子的数量。首次适应算法将每件物品放入第一个有足够剩余空间的箱子。
First-Fit Decreasing (FFD) first sorts items into decreasing order of size, then applies First-Fit. This heuristic usually yields a better (fewer bins) solution.
递减首次适应算法先将物品按大小降序排列，再应用首次适应。这种启发式方法通常能得到更优（更少箱子）的解。
Example: ] (10), Bin3: [7] (7) → 3 bins. FFD sorts to: 8,7,5,4,2,1. Packing: Bin1: [8,2], Bin2: [7,?,?] 5 doesn’t fit with 7? Cap 10, 7+5=12 >10, so Bin2: [7,?,?] next best 4? 7+4=11 no, 7+2=9 then 1? 7+2+1=10 → Bin1: [8,2], Bin2: [7,2,1]? Wait 7+2+1=10, so Bin1: [8,?] 8+2? After sorting, items: 8,7,5,4,2,1. FFD: Bin1: [8,2] (10), Bin2: [7,?] 7+3? → 3 bins. Here both FF and FFD give 3 bins, but FFD is often better for larger instances.
示例：箱容量为 10，物品为 4, 8, 1, 5, 2, 7。FF 装箱：箱1：[4,1,5]（总和 10），箱2：[8,2]（10），箱3：[7]（7）→ 3 箱。FFD 排序：8,7,5,4,2,1。箱1：[8,2]，箱2：[7,2,1]? 等等。物品为 8,7,5,4,2,1，箱1：[8,2] (10)，箱2：[7,2,1] 中 2 已用？实际需顺序放置：8进箱1，7进箱2，5试箱1：8+5=13>10，试箱2：7+5=12>10，新箱3：[5]，4试箱1：8+4=12>10，箱2：7+4=11>10，箱3：5+4=9 → 4进箱3得[5,4]，2试箱1：8+2=10 → 入箱1得[8,2]，1试箱1满，试箱2：7+1=8 → 入箱2得[7,1]，至此箱1:[8,2],箱2:[7,1],箱3:[5,4]共3箱。FFD仍为3箱，但通常更优。
7. Critical Path Analysis | 关键路径分析
Critical path analysis (CPA) is used in project management to determine the minimum project duration and identify critical activities that cannot be delayed without affecting the total project time.
关键路径分析用于项目管理，以确定最短项目工期，并识别不可延误的关键活动，这些活动若延迟将影响总工期。
t finish (LFT). Float = LST − EST (or LFT − EFT). Activities with zero float are critical.
给定活动节点网络，先进行正向遍历计算最早开始时间和最早完成时间。再进行反向遍历得到最晚开始时间和最晚完成时间。总浮动时间 = LST − EST（或 LFT − EFT）。浮动时间为零的活动即为关键活动。
FT of B=7, LST=3. LFT of C=7, LST=5. LFT of A=min(3,5)=3, LST=0. Floats: A=0, B=0, C=7−5−2? Wait float of C = LST−EST = 5−3=2, D=0. Critical path: A–B–D.
示例：活动：A(3)，B(4)依赖于A，C(2)依赖于A，D(5)依赖于B和C。从时间0开始。正向：A最早开始=0，完成=3；B开始=3，完成=7；C开始=3，完成=5；D开始=max(7,5)=7，完成=12。项目工期12。反向：D最晚完成=12，开始=7；B完成=7，开始=3；C完成=7，开始=5；A完成=min(3,5)=3，开始=0。浮动时间：A=0，B=0，C=5−3=2，D=0。关键路径：A–B–D。
8. Linear Programming: Graphical Approach | 线性规划：图解法
Linear programming (LP) deals with maximising or minimising a linear objective function, subject to linear inequality constraints. In two variables, the feasible region is a polygon, and the optimal solution occurs at a vertex (corner) of this region.
线性规划处理在若干线性不等式约束下最大化或最小化一个线性目标函数的问题。在两个变量的情况下，可行域是一个多边形，最优解必在可行域的某个顶点（角点）达到。
Steps: 1) Formulate the constraints and objective. 2) Graph the constraints, shading the feasible region. 3) Find the coordinates of all vertices. 4) Evaluate the objective at each vertex to find the optimum. Alternatively, use an objective line method.
步骤：1）列出约束条件和目标函数；2）画出约束条件，标出可行域；3）求出所有顶点的坐标；4）计算每个顶点处的目标函数值以找出最优解。也可使用目标函数等值线法。
Example: 2x+y=8, (4,0). P values: at (0,0) 0, (0,6) 12, (4,0) 12, (4,2) 16. Maximum P=16 at (4,2).
示例：最大化 P = 3x + 2y，约束为 x + y ≤ 6，x ≥ 0，y ≥ 0，2x + y ≤ 8。顶点：(0,0)，(0,6)，由 x+y=6 与 2x+y=8 得 (4,2)，(4,0)。P 值：(0,0)=0，(0,6)=12，(4,0)=12，(4,2)=16。最大 P=16 在 (4,2) 达到。
9. Dijkstra’s Algorithm for Shortest Path | Dijkstra 最短路径算法
Dijkstra’s algorithm finds the shortest path from a start node to all other nodes in a weighted graph with non-negative edge weights. It uses labels (distance, previous node) and updates them iteratively from the current node.
Dijkstra 算法用于在边权非负的带权图中找出从起始节点到所有其他节点的最短路径。它使用标签（距离，前驱节点）并从当前节点出发迭代更新。
tart as permanent. Among the nodes reachable from permanent nodes, update their temporary distances if a shorter route is found. Select the node with smallest temporary distance and make it permanent. Repeat until all nodes permanent.
算法：将起始节点的临时距离设为 0，其他节点设为 ∞。将起始节点标记为永久。从永久节点可达的节点中，若找到更短路径则更新其临时距离。选择临时距离最小的节点，将其永久化。重复至所有节点永久化。
Example: Graph with nodes A,B,C,D; edges: A–B=4, A–C=2, B–C=1, B–D=5, C– : to D, 3+5=8 <10, so update D=8 from B. Make D permanent (8). Shortest paths: A→C→B→D =8.
示例：图包含节点 A,B,C,D；边：A–B=4，A–C=2，B–C=1，B–D=5，C–D=8。起点 A。永久 A(0)。从 A：临时 B=4，C=2。将 C 永久化 (2)。从 C：到 D 2+8=10，到 B 2+1=3 < 4，更新 B=3 来自 C。将 B 永久化 (3)。从 B：到 D 3+5=8 <10，更新 D=8 来自 B。将 D 永久化 (8)。最短路径：A→C→B→D =8。
10. Kruskal’s Algorithm for Minimum Spanning Tree | Kruskal 最小生成树算法
Kruskal’s algorithm builds a minimum spanning tree (MST) of a connected weighted graph by repeatedly adding the smallest available edge that does not form a cycle, until all vertices are connected.
Kruskal 算法通过反复添加不构成环的最小可用边来构建连通带权图的最小生成树，直到所有顶点连通。
Procedure: Sort all edges by weight in ascending order. Starting with an empty forest, for each edge, if it joins two different trees (different components), add it to the MST; otherwise discard it. Continue until the MST has V−1 edges for V vertices.
步骤：将所有边按权重升序排列。从空森林开始，对每条边，若它连接两棵不同的树（不同分量），则加入 MST；否则舍弃。直到 MST 包含 V−1 条边（V 为顶点数）。
). Add AD(1) → connects A,D. Add BD(2) → connects B to A,D. Add AB(3) → would form cycle A–B–D–A? eck AC(5): A and C now in same component (through B), discard. CD(6): C and D in same, discard. MST edges: AD, BD, AB? ded, that’s 3 edges: AD, BD, BC. Total weight = 1+2+4=7. Check connectivity: all connected? A–D, D–B, B–C, yes.
示例：图边：AB(3), AC(5), AD(1), BC(4), BD(2), CD(6)。排序：AD(1), BD(2), AB(3), BC(4), AC(5), CD(6)。加入 AD(1) → 连通 A,D。加入 BD(2) → B 与 A,D 连通。AB(3) 会形成环 A–B–D–A，舍弃。加入 BC(4) → 连通 C。此后 AC(5) 中 A 与 C 已在同一分量（通过 B），舍弃。CD(6) 同理舍弃。MST 边：AD, BD, BC 共 3 条，总权重 7。连通性：A–D, D–B, B–C，成立。
11. Sorting Networks | 排序网络
A sorting network uses a fixed sequence of comparators to sort a list of numbers. Each comparator takes two inputs and outputs them in order (smaller to top, larger to bottom). Parallel comparators can operate simultaneously, allowing efficient hardware implementation.
排序网络使用一组固定的比较器序列对数字列表进行排序。每个比较器接收两个输入，并按顺序输出（较小者在上，较大者在下）。并行比较器可同时工作，便于硬件高效实现。
For example, a sorting network for three inputs uses three comparators in a specific pattern to guarantee sorted output regardless of initial order. The “bubble” or “odd–even” networks are common in A-Level D1.
例如，一个三输入排序网络使用三个比较器按特定模式连接，保证无论初始顺序如何均能输出排序结果。“气泡”或“奇偶”网络在 A-Level D1 中常见。
To trace a sorting network, write values on the input wires and apply each comparator step-by-step, swapping if necessary. The final state gives the sorted list.
要追踪排序网络，在输入线上写下值，逐步应用每个比较器，必要时进行交换。最终状态即为排序列表。
Published by TutorHao | Mathematics Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图