📚 A-Level Edexcel Programming: Algorithms, Searching, Sorting and Complexity | 爱德思 A-Level 编程：算法、搜索、排序与复杂度
In Edexcel A-Level Computer Science, programming questions require more than writing code. You must understand how algorithms work, trace their behaviour, compare efficiency using Big-O notation, and choose the right standard algorithm for a given problem. This revision article covers algorithmic thinking, pseudocode, linear and binary search, bubble, insertion and merge sort, as well as complexity analysis and exam technique. Use the paired English and Chinese explanations to strengthen both technical vocabulary and conceptual understanding.
在爱德思 A-Level 计算机科学中，编程题考查的不仅是编写代码。你必须理解算法的工作原理，跟踪其执行过程，使用大 O 表示法比较效率，并为给定问题选择合适的标准算法。本文涵盖算法思维、伪代码、线性搜索和二分搜索、冒泡排序、插入排序和归并排序，以及复杂度分析和考试技巧。使用中英对照的讲解，可以同时加强技术词汇和概念理解。
1. Algorithmic Thinking and Abstraction | 算法思维与抽象
Algorithmic thinking means breaking a problem into clear, ordered steps and identifying the inputs, processes, outputs and storage needed before writing code. Abstraction reduces complexity by removing unnecessary details, leaving only the features relevant to the solution. In the Edexcel specification, this skill is tested through trace tables, pseudocode interpretation and code analysis. For example, modelling a school register as a list of student records uses abstraction because it ignores features such as height or favourite colour unless they affect attendance.
算法思维意味着把问题分解为清晰、有序的步骤，并在编写代码前确定所需的输入、处理、输出和存储。抽象通过移除不必要的细节来降低复杂度，只保留与解决方案相关的特征。在爱德思考试规范中，这一技能通过跟踪表、伪代码解释和代码分析进行考查。例如，将学校点名册建模为学生记录的列表，就是使用了抽象，因为它忽略了身高或喜好颜色等与出勤无关的特征。
2. Pseudocode Essentials | 伪代码基础
Edexcel uses a defined pseudocode style for exam responses. You should use keywords such as SET, IF…THEN…ELSE, WHILE, FOR, REPEAT…UNTIL, INPUT, OUTPUT and RETURN. Assignment uses the left arrow symbol <- rather than an equals sign. Indentation is used to show block structure, and logical conditions must be written clearly. Pseudocode is marked for correct control flow and problem-solving logic, not for language-specific syntax, so avoid using features such as print() or console.log unless the question explicitly allows them.
爱德思在考试答题中使用规定的伪代码风格。你应该使用 SET、IF…THEN…ELSE、WHILE、FOR、REPEAT…UNTIL、INPUT、OUTPUT 和 RETURN 等关键字。赋值使用左箭头符号 <-，而不是等号。缩进用于表示代码块结构，逻辑条件必须书写清楚。伪代码的评分依据是控制流程和问题解决逻辑是否正确，而不是特定语言语法，因此除非题目明确允许，否则避免使用 print() 或 console.log 等功能。
3. Linear Search | 线性搜索
A linear search checks each element of a list in order from the beginning until the target value is found or the end of the list is reached. It works on both unsorted and sorted data and requires no preparation. The worst case occurs when the target is at the end or missing, requiring n comparisons for a list of length n. A simple pseudocode implementation sets an index i to 0, then loops while i is less than the list length and the current element is not equal to the target. If the loop ends with i within the list bounds, the target has been found.
线性搜索从列表开头按顺序检查每个元素，直到找到目标值或到达列表末尾。它适用于未排序和已排序的数据，不需要任何准备工作。最坏情况发生在目标值位于末尾或不存在时，长度为 n 的列表需要进行 n 次比较。一个简单的伪代码实现将索引 i 设为 0，然后在 i 小于列表长度且当前元素不等于目标值时循环。如果循环结束时 i 仍位于列表范围内，则说明已找到目标。
4. Binary Search | 二分搜索
Binary search works only on sorted lists. It repeatedly compares the middle element with the target value. If they match, the search stops. If the target is smaller, the search continues in the left half; if larger, it continues in the right half. Each step halves the remaining search space, producing a logarithmic time complexity O(log n). Pseudocode uses low, mid and high pointers. A WHILE loop continues as long as low is less than or equal to high. If the target is not found, the algorithm returns a suitable indicator such as -1.
二分搜索仅适用于已排序列表。它不断将中间元素与目标值进行比较。如果两者匹配，搜索停止。如果目标值较小，则在左半部分继续搜索；如果较大，则在右半部分继续搜索。每一步都将剩余搜索空间减半，因此产生对数时间复杂度 O(log n)。伪代码使用 low、mid 和 high 三个指针。当 low 小于或等于 high 时，WHILE 循环继续执行。如果未找到目标，算法返回合适的指示值，如 -1。
5. Comparing Search Algorithms | 搜索算法比较
Linear search is simpler and works on unsorted data, but its O(n) growth makes it slow for very large lists. Binary search is much faster with O(log n) complexity, but it requires sorted data and more complex logic. In exam questions, you may need to choose an appropriate algorithm and justify your choice with reference to data size, preparation cost and readability. The table below summarises the key differences.
线性搜索更简单，适用于未排序数据，但其 O(n) 的增长在大型列表上会变得很慢。二分搜索的复杂度为 O(log n)，速度快得多，但需要已排序数据和更复杂的逻辑。在考试题中，你可能需要选择合适的算法，并根据数据规模、准备成本和可读性说明理由。下表总结了主要区别。
| Feature | Linear Search | Binary Search |
|---|---|---|
| Data requirement | Any list | Sorted list |
| Worst-case time | O(n) | O(log n) |
| Best-case time | O(1) | O(1) |
| Use case | Small or unsorted data | Large sorted data |
6. Bubble Sort | 冒泡排序
Bubble sort repeatedly compares adjacent elements and swaps them if they are in the wrong order. After each full pass through the list, the largest unsorted element moves to its final position at the end, like a bubble rising to the surface. It is simple to understand and implement, but inefficient for large data sets because its worst-case and average-case complexity is O(n²). Pseudocode uses two nested loops: an outer loop to control passes and an inner loop to compare adjacent pairs up to the unsorted boundary.
冒泡排序不断比较相邻元素，如果顺序错误就交换它们。每次完整遍历列表后，最大的未排序元素会移到末尾的最终位置，就像气泡升到水面一样。它简单易懂、易于实现，但对大型数据集效率较低，因为其最坏情况和平均情况的复杂度都是 O(n²)。伪代码使用两个嵌套循环：外层循环控制遍历次数，内层循环比较相邻元素，直到未排序边界。
7. Insertion Sort | 插入排序
Insertion sort builds a sorted sublist by taking each new element and inserting it into its correct position among the already sorted elements to its left. It works well for small lists or lists that are nearly sorted, and it is a stable sorting algorithm because equal elements keep their relative order. In the worst case it requires O(n²) comparisons, but when data is already sorted it runs in O(n). This makes insertion sort a practical option when frequent additions to a sorted list are needed.
插入排序通过逐个取出新元素并将其插入到左侧已排序部分的正确位置来构建有序子列表。它适用于小型列表或基本有序的列表，并且是一种稳定的排序算法，因为相等元素的相对顺序保持不变。在最坏情况下需要 O(n²) 次比较，但当数据已经有序时只需要 O(n)。因此，当需要频繁向有序列表中添加元素时，插入排序是一个实用的选择。
8. Merge Sort | 归并排序
Merge sort uses a divide-and-conquer strategy. It recursively splits the list into halves until each sublist contains a single element, then repeatedly merges these sublists back together in sorted order. The merge step compares the smallest remaining elements of the two sublists and places the smaller one into the output. Merge sort has O(n log n) time complexity in all cases, which makes it very efficient for large data sets. However, it needs extra memory for temporary sublists, so it is less suitable when memory is very limited.
归并排序采用分治策略。它递归地将列表分成两半，直到每个子列表只包含一个元素，然后不断地按排序顺序将这些子列表合并回来。合并步骤比较两个子列表中剩余的最小元素，并将较小的元素放入输出中。归并排序在所有情况下的时间复杂度都是 O(n log n)，因此对大型数据集非常高效。但是，它需要额外的内存来存储临时子列表，因此在内存非常有限的情况下不太适合。
9. Big-O Notation and Algorithm Efficiency | 大 O 表示法与算法效率
Big-O notation describes how an algorithm’s runtime or memory usage grows as the input size n increases. Constant time O(1) does not depend on n. Linear time O(n) grows in direct proportion to n. Quadratic time O(n²) grows much faster and becomes impractical for large n, as seen in bubble sort. Logarithmic time O(log n) grows slowly because the problem size is halved each step, as in binary search. Linearithmic time O(n log n) is typical of efficient sorting algorithms such as merge sort. When comparing algorithms, always state the Big-O category and the context.
大 O 表示法描述算法的运行时间或内存使用如何随输入规模 n 增加而增长。常数时间 O(1) 不依赖 n。线性时间 O(n) 与 n 成正比增长。二次方时间 O(n²) 增长更快，对大型 n 不实用，冒泡排序就是如此。对数时间 O(log n) 增长缓慢，因为问题规模每一步减半，二分搜索就是如此。线性对数时间 O(n log n) 是归并排序等高效排序算法的典型特征。在比较算法时，一定要说明大 O 类别和具体情境。
10. Standard Algorithms in Practice | 标准算法实战
Edexcel exam questions may ask you to trace an algorithm line by line, identify a logical error, or write a modified version of a standard algorithm. When tracing, use a table to record each variable’s value at every loop iteration. When designing a solution, select an algorithm based on the data: use binary search only if the list is sorted, merge sort for large lists where stability is not required, and insertion sort for small or nearly sorted lists. Be ready to discuss space-time trade-offs and justify your choice with reference to the problem constraints.
爱德思考试题可能要求你逐行跟踪算法、找出逻辑错误，或编写标准算法的修改版本。跟踪时，使用表格记录每个变量在每次循环迭代中的值。在设计解决方案时，根据数据选择算法：只有列表已排序才能使用二分搜索；大型列表且不要求稳定性时使用归并排序；小型或基本有序的列表使用插入排序。准备好讨论时间与空间的权衡，并根据问题约束说明你的选择。
11. Common Pitfalls and Exam Tips | 常见错误与备考建议
A frequent mistake is applying binary search to an unsorted list, which produces incorrect results. Another common error is an off-by-one loop condition, especially when using WHILE with lists indexed from 0. Make sure every loop has a terminating condition and every variable is initialised before use. In trace tables, update all variables consistently at each step. When answering efficiency questions, avoid vague statements such as ‘this algorithm is fast’. Instead, give the Big-O category and explain what that means for doubling the input size. Use clear, exam-style wording in every answer.
一个常见错误是对未排序列表使用二分搜索，这会产生错误结果。另一个常见错误是循环条件出现 off-by-one 错误，尤其是在列表索引从 0 开始的情况下使用 WHILE 时。确保每个循环都有终止条件，每个变量在使用前都已初始化。在跟踪表中，每一步都要一致地更新所有变量。回答效率问题时，避免使用“这个算法很快”之类的模糊说法。相反，应给出大 O 类别，并解释当输入规模翻倍时这意味着什么。每道题的答案都要使用清晰、符合考试风格的措辞。
Published by TutorHao | Programming Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导Cancel reply