AQA GCSE Computer Science 算法 搜索 排序 流程
AQA GCSE 计算机科学的算法部分是 Paper 1 的必考内容。很多同学背下了冒泡排序的每一行伪代码，却在问「为什么这里要用二分搜索」时答不上来。真正的得分点是理解每个算法的适用条件与代价：数据是否有序、比较次数如何增长、内存开销有多大。这篇文章用中英双语梳理 AQA 要求掌握的全部算法考点，从计算思维、伪代码与流程图，到线性搜索、二分搜索、冒泡排序、归并排序的效率比较，最后给出考场上的答题模板与常见失分点。适合 Year 10 到 Year 11 复习，也适合国际学校转轨的学生补齐计算机词汇。
Algorithms sit at the heart of AQA GCSE Computer Science Paper 1. Many students can memorise every line of bubble sort pseudocode yet cannot explain when binary search is worth using. The marks are earned by reasoning about trade-offs: is the data sorted, how do the number of comparisons grow, and how much extra memory does the method need? This guide covers the full AQA algorithm specification in Chinese and English, moving from computational thinking and pseudocode to linear search, binary search, bubble sort and merge sort, then finishes with exam technique and the mistakes that cost the most marks.
1. 计算思维：分解、抽象与算法思维
AQA 要求学生能用三种思维方式分析问题。分解 (decomposition) 是把大问题拆成可以单独解决的小问题，例如把「做一个成绩查询系统」拆成「录入分数」「排序」「按名字查找」「显示结果」。抽象 (abstraction) 是只保留解决问题必需的信息，忽略其余细节：计算班级平均分时不需要知道每个学生的生日和家庭住址。算法思维 (algorithmic thinking) 是把解决步骤写成清晰的、有限的、可执行的序列，让任何人在同样的输入下都能得到同样的输出。考试中常见的问法是「用抽象说明为什么这个模型只保留三条信息」，答题时必须点出被删掉的信息以及删掉之后仍然能解决问题的理由，只写「因为更简单」不得分。
AQA expects you to reason with three thinking tools. Decomposition breaks a large problem into smaller problems that can be solved separately: a results-lookup system splits into entering marks, sorting them, searching by name, and displaying the outcome. Abstraction keeps only the information needed to solve the problem and discards the rest, so calculating a class average does not require any student's birthday or home address. Algorithmic thinking turns the solution into a clear, finite, executable sequence so that anyone following it with the same input reaches the same output. When a question says "explain how abstraction is used in this model", the mark scheme wants the deleted detail and the reason the solution still works without it. Writing "because it is simpler" gains nothing.
2. 伪代码与流程图：Representing Algorithms
AQA 规定用统一的伪代码风格书写算法，关键字通常大写，常见结构包括 IF ... THEN ... ELSE ... ENDIF、WHILE ... ENDWHILE、REPEAT ... UNTIL、FOR i IN range(0, n)，以及用于数组的 array[index]。整数除法写 DIV，取余写 MOD。流程图 (flowchart) 中的菱形代表判断 (decision)，矩形代表处理 (process)，平行四边形代表输入输出 (input/output)，带箭头的线代表流程方向。写伪代码时两个细节最容易失分：一是循环的条件必须能终止，二是数组下标从 0 开始，遍历长度为 n 的数组应写 range(0, n) 而不是 range(1, n)。考试中如果题目要求「用伪代码写出」，就必须使用规定的关键字，不能用 Python 的 def 或 Java 的 public static 来替代，否则语法分全部丢失。
AQA uses a single agreed pseudocode style in which keywords are usually written in capital letters. The essential structures are IF ... THEN ... ELSE ... ENDIF, WHILE ... ENDWHILE, REPEAT ... UNTIL, and FOR i IN range(0, n), with square brackets for array indexing. Integer division is DIV and remainder is MOD. In a flowchart, a diamond means a decision, a rectangle a process, a parallelogram an input or output, and arrows show the direction of flow. Two details lose marks most often: a loop condition that can never end, and off-by-one indexing, since arrays start at 0 and looping over n items means range(0, n), not range(1, n). If the question says "write in pseudocode", you must use the AQA keywords. Substituting Python def or Java public static forfeits the syntax marks entirely.
3. 线性搜索与二分搜索：Linear and Binary Search
线性搜索 (linear search) 从头到尾逐个比较，找到目标就停止。它对数据没有要求，任何顺序都能用，但最坏情况下要比较 n 次，n 是数据项个数。二分搜索 (binary search) 要求数据已经排序，每次取中间项比较：目标大于中间项就丢掉左半部分，小于就丢掉右半部分，等于就返回位置。长度为 1000 的列表，线性搜索最坏要比较 1000 次，二分搜索最多约 10 次，因为每比较一次数据规模就减半。考场问「为什么二分搜索更快」时，标准答案是「每次比较都把待查范围减半，因此比较次数以对数方式增长」，只说「因为它聪明」不得分。反过来问「什么情况下不能用二分搜索」，答案是数据未排序，或者列表在查找过程中会被频繁修改，因为维护有序状态本身需要额外的排序开销。
A linear search compares items one by one from the start and stops when the target is found. It works on data in any order, but in the worst case it needs n comparisons for n items. A binary search requires sorted data and tests the middle item each time: if the target is greater, the left half is discarded; if smaller, the right half goes; if equal, the position is returned. For a list of 1000 items, a linear search may need 1000 comparisons while a binary search needs about 10, because every comparison halves the remaining data. Asked why binary search is faster, the mark-scheme answer is that each comparison halves the search range so the number of comparisons grows logarithmically. Asked when binary search cannot be used, the answer is that the data is unsorted, or that the list is modified so often that keeping it ordered costs more than the search saves.
4. 冒泡排序与归并排序：Sorting Algorithms
冒泡排序 (bubble sort) 反复比较相邻两项，顺序错误就交换，每一轮把当前最大的元素「冒」到末尾。长度为 n 的列表最多需要 n 减 1 轮；如果某一轮没有发生任何交换，说明已经有序，可以提前结束，这一点在题目要求「写出更高效的版本」时必须体现。归并排序 (merge sort) 采用分治思路：先把列表不断对半拆分，直到每个子列表只剩一个元素，然后把有序子列表两两合并，合并时总是先取两个子列表中最小的那一项。归并排序的比较次数明显少于冒泡排序，但需要额外的存储空间来放合并结果，这是它的代价。AQA 也要求掌握插入排序 (insertion sort)：把每个新元素插入到前面已排好序的部分中的正确位置，适合数据量小或数据接近有序的场景。
Bubble sort repeatedly compares adjacent pairs and swaps them when they are in the wrong order, so on each pass the largest remaining item bubbles to the end. A list of n items needs at most n minus 1 passes, and if a pass makes no swaps the list is already sorted, so the algorithm can stop early. Stating that early exit is what earns the improvement marks. Merge sort divides the list in half again and again until each sub-list holds one item, then merges sorted sub-lists pairwise, always taking the smaller of the two front items. It makes far fewer comparisons than bubble sort but needs extra memory for the merged results, which is the trade-off. AQA also requires insertion sort: each new item is inserted into its correct place within the already sorted part, which suits small or nearly ordered data sets.
5. 算法效率：Efficiency and Comparison Counts
效率不等于「代码行数少」，而是看随着数据量增长，比较次数和内存占用如何变化。比较的基准是：线性搜索随数据量线性增长，二分搜索在数据翻倍时只多一次比较；冒泡排序在大列表上比较次数按平方增长，归并排序按 n 乘以对数增长。考试中常给出的表格题会列出不同数据量下的比较次数，让你判断某个算法是否符合要求。答题时要点出三点：数据规模、增长方式、以及是否需要额外内存。举例说明：在 8000 条记录中查找一个学号，线性搜索最坏需要 8000 次比较，二分搜索最多约 13 次，因此在数据有序时二分搜索是正确选择；但如果这 8000 条记录每小时都在更新，维护有序的成本可能超过搜索节省的开销。
Efficiency is not about writing fewer lines of code; it is about how the number of comparisons and the memory use change as the data grows. The benchmarks are these: a linear search grows in proportion to the data, while a binary search needs only one more comparison each time the data doubles. Bubble sort grows with the square of the data, whereas merge sort grows with n multiplied by a logarithm. Exam tables often show comparison counts for different data sizes and ask you to judge whether an algorithm meets a requirement, so answer with three elements: the size of the data, the way the cost grows, and whether extra memory is needed. For example, searching a student number among 8000 records takes up to 8000 comparisons linearly but about 13 with binary search, so sorted data favours binary search. If those 8000 records change every hour, however, keeping them ordered may cost more than the search saves.
6. 追踪表与考试技巧：Trace Tables and Exam Technique
追踪表 (trace table) 是 AQA 算法题的核心工具：每一列是一个变量，每一行是算法执行的一步，按顺序填入变量值和输出。填写时要注意循环变量的初值、判断条件的真假分支以及数组越界的情况，漏写中间某一次循环是常见的失分点。Paper 1 的计算思维与编程技能部分时间为 1 小时 30 分钟，算法题常与程序设计题连在一起，建议先做算法设计与效率比较题，把需要仔细走查的追踪表放在最后，因为追踪表容易在一个小错误上耗费时间。回答「用伪代码实现」这类题时，先把结构和循环边界写清楚，再补细节，比直接从头写到底更容易拿到结构分。平时练习建议限时 15 分钟完成一道完整的搜索或排序题，包括伪代码、追踪表与效率说明。
The trace table is the central tool for AQA algorithm questions: each column is a variable, each row a step of execution, and you fill in values and outputs in order. Watch the initial value of the loop counter, which branch each condition takes, and whether an index runs out of range; skipping one iteration is the classic lost mark. Paper 1 covers computational thinking and programming skills in 1 hour 30 minutes, and algorithm questions usually run straight into programming questions, so do the design and efficiency comparisons first and leave detailed trace tables until later, since one small slip can swallow a lot of time. For "write pseudocode" questions, get the structure and loop boundaries right before adding detail: structure marks come first. In practice, time yourself to 15 minutes for a full search or sort question including pseudocode, trace table and efficiency explanation.
7. 实例演练：在有序表中查找与比较次数计算 Worked Example
假设有一个已排序的数组 [12, 25, 33, 47, 58, 61, 74, 90]，要查找 61。二分搜索先取中间项：长度为 8，中点取下标 3 的元素 47。61 大于 47，丢弃左半部分，剩下 [58, 61, 74, 90]，范围长度为 4。再取中点，找到 58；61 大于 58，丢弃左半部分，剩下 [61, 74]，范围长度为 2。再取中点得到 61，比较成功，返回下标 5。整个过程只比较了 3 次。如果用线性搜索，需要依次比较 12、25、33、47、58、61，共 6 次。这个例子说明两点：一是范围每比较一次大约减半，二是二分搜索的比较次数取决于数据量而不是目标位置。如果目标值不存在，二分搜索会在范围缩小到空之后结束并报告未找到，这也是答题时必须写出的「终止条件」。
Take the sorted array [12, 25, 33, 47, 58, 61, 74, 90] and search for 61. The binary search tests the middle of eight items, index 3, which holds 47. Since 61 is greater, the left half is discarded and the range becomes [58, 61, 74, 90] with length 4. The middle is now 58, and because 61 is greater, the left half goes again, leaving [61, 74] with length 2. The middle item is 61, so the search succeeds and returns index 5 after only three comparisons. A linear search would compare 12, 25, 33, 47, 58 and 61, six comparisons in total. Two lessons follow: the range roughly halves with every comparison, and the number of comparisons depends on the size of the data rather than on where the target sits. When the target is absent, a binary search ends once the range is empty and reports not found, and that stopping condition is a required part of a full-mark answer.
8. 常见失分点与得分要点 Common Mistakes
第一，把二分搜索用在未排序的数据上，或者没有说明数据必须先排序。第二，写冒泡排序时忘记提前结束条件，或者把内层循环的边界写成完整长度，导致比较已排好的元素。第三，混淆 DIV 与 MOD，例如判断奇偶时应该用 MOD 2 而不是 DIV 2。第四，解释效率时只写「更快」而不写比较次数或增长方式，这类答案通常不给分。第五，在伪代码中使用 Python 或 Java 的语法。第六，追踪表只写最终结果，不写中间过程。复习时把每一条对应到一个具体例题，比重复抄写算法更有效。
First, using binary search on unsorted data, or failing to state that the data must be sorted first. Second, writing bubble sort without the early-exit condition, or letting the inner loop run across the whole array and compare items that are already in place. Third, confusing DIV with MOD, for instance using DIV 2 rather than MOD 2 to test for an odd number. Fourth, explaining efficiency with the word faster alone instead of naming the comparison count or the growth pattern, which rarely earns the mark. Fifth, mixing Python or Java syntax into pseudocode answers. Sixth, filling a trace table with only the final value and no intermediate steps. Revising means attaching every one of these rules to a concrete past-paper question rather than copying algorithms out again.
把算法学扎实的关键是「能解释」而不是「能背诵」。当你能说清楚一个算法为什么需要有序数据、每次比较后剩下的范围有多大、以及它比另一个算法多花多少内存时，无论题目怎么变化，你都能顺着逻辑写出答案。建议每周挑两道 AQA 真题，完整写出伪代码、追踪结果并说明效率，坚持一个月，Paper 1 的算法题基本可以稳定拿分。
The key to mastering algorithms is being able to explain them, not recite them. Once you can say why an algorithm needs sorted data, how large the remaining range is after each comparison, and how much extra memory it costs compared with another method, you can reason your way to the answer no matter how the question is worded. Pick two AQA past-paper questions each week, write the pseudocode in full, trace the values and justify the efficiency. Do that for a month and the algorithm questions in Paper 1 become reliable marks.
戴睿（dere）Neo优选系列 创意双触摸屏高性能笔记本电脑大学生AI学习商务办公设计炒股娱乐手提轻薄本32/1TB¥4586.0📱 去京东购买京东精选
需要一对一辅导？Need One-on-One Tutoring?
A-Level / GCSE / IB / KS2-KS3 全科辅导
16621398022 同微信
Visit aleveler.com
或截图后用「扫一扫 → 相册」选择本图