📚 IB WJEC Computer Science: Algorithms Revision | IB WJEC计算机：算法考点精讲
Mastering algorithms is crucial for both IB Computer Science and WJEC specifications. Whether you are tackling IB's Paper 1 or WJEC's Unit 2, a solid grasp of algorithmic thinking, representation methods, and efficiency analysis is essential for top marks. This article breaks down every key topic, from basic constructs to Big O notation, with clear bilingual explanations and exam-focused insights.
掌握算法对于IB计算机科学和WJEC考试都至关重要。无论你面对的是IB的Paper 1还是WJEC的Unit 2，扎实掌握算法思维、表示方法和效率分析都是取得高分的关键。本文将详细解析从基本结构到大O表示法的每一个核心主题，提供清晰的双语讲解与应试导向的深度解析。
1. What is an Algorithm? | 什么是算法？
An algorithm is a finite sequence of well-defined, unambiguous steps that takes an input, processes it, and produces an output. It must always terminate after a finite number of steps and solve the intended problem completely.
算法是一系列定义明确、无歧义的有限指令步骤，它接收输入、对其进行处理并产生输出。它必须在有限步之内终止，并完整地解决预期问题。
Every valid algorithm exhibits five key characteristics: finiteness (it ends), definiteness (each step is precisely stated), input (zero or more inputs), output (at least one output), and effectiveness (each step is basic enough to be carried out).
每个正确的算法都具有五个关键特性：有穷性（能够终止）、确定性（每一步都精确无歧义）、输入（零个或多个输入）、输出（至少一个输出）和可行性（每一步都可以在有限时间内完成）。
Algorithms are not tied to any specific programming language; they are abstract solutions that can be implemented in Python, Java, pseudocode, or any other notation.
算法不依赖任何特定的编程语言；它们是抽象的解决方案，可以用Python、Java、伪代码或其他任何表示法来实现。
2. Representing Algorithms: Flowcharts & Pseudocode | 算法的表示：流程图与伪代码
Algorithms can be expressed visually using flowcharts. Standard symbols connected by arrows show the flow of control: an oval marks start/end, a parallelogram denotes input/output, a rectangle represents a process or calculation, and a diamond indicates a decision or condition.
算法可以用流程图直观表达。通过箭头连接的标准符号展示控制流：椭圆形标记开始/结束，平行四边形表示输入/输出，矩形代表处理或计算步骤，菱形表示判断或条件。
For example, a flowchart to read a number and output its double would begin with an oval 'Start', then a parallelogram 'Read n', then a rectangle 'result ← n × 2', then a parallelogram 'Output result', and end with an oval 'Stop'.
例如，读取一个数字并输出其双倍值的流程图，会以椭圆形"开始"起步，然后是平行四边形"读取 n"，接着是矩形"result ← n × 2"，再是平行四边形"输出 result"，最后以椭圆形"停止"结束。
Pseudocode is a structured, language-independent way to write algorithms using plain English and common programming constructs like IF, WHILE, FOR, and CASE. It focuses on logic rather than syntax details. Both IB and WJEC provide their own pseudocode reference guides, but the underlying principles remain identical.
伪代码是一种结构化、与语言无关的算法表述方式，使用通俗英语和常见的编程结构（如IF、WHILE、FOR、CASE）。它注重逻辑而非语法细节。IB和WJEC虽然提供各自的伪代码参考指南，但其根本原则是完全一致的。
A simple pseudocode example to compute a running total: sum ← 0, FOR count ← 1 TO 10, sum ← sum + count, ENDFOR. The arrow ← denotes assignment, and the indentation clarifies the loop body.
一个计算累加和的简单伪代码例子：sum ← 0，FOR count ← 1 TO 10，sum ← sum + count，ENDFOR。箭头←表示赋值，缩进则清晰标明了循环体。
3. Basic Constructs: Sequence, Selection & Iteration | 基本结构：顺序、选择与迭代
All algorithms are constructed from three fundamental control structures. Sequence means executing instructions one after another in the order they appear. This is the default flow in any program.
所有算法都由三种基本控制结构构建而成。顺序是指按照指令出现的先后次序逐条执行，这是任何程序中的默认流程。
Selection allows the algorithm to make decisions. The common forms are IF...THEN...ELSE and CASE/switch structures. In IB pseudocode, you might see IF condition THEN ... ELSE ... ENDIF, while WJEC uses similar constructs. Selection provides branching based on Boolean conditions.
选择使算法能够做判断。常见的形式有IF...THEN...ELSE和CASE/switch结构。在IB伪代码中可能看到IF condition THEN ... ELSE ... ENDIF，WJEC也使用类似的构造。选择基于布尔条件提供分支路径。
Iteration repeats a block of code. There are pre-conditional loops such as WHILE condition DO ... ENDWHILE, where the condition is checked before each iteration, and post-conditional loops like REPEAT ... UNTIL condition, where the body executes at least once. Counted loops using FOR index ← start TO end are also essential.
迭代重复执行一段代码。前测试循环比如WHILE condition DO ... ENDWHILE，每次迭代前检查条件；后测试循环如REPEAT ... UNTIL condition，循环体至少执行一次。使用FOR index ← start TO end的计数循环也是必不可少的。
4. Standard Algorithms: Counting, Summing & Finding Extremes | 标准算法：计数、求和与寻找最值
Exam questions frequently ask you to write or trace standard algorithms. These include counting specific occurrences in a list, summing all elements, calculating an average, and identifying the maximum or minimum value.
考题经常要求你编写或跟踪标准算法，例如统计列表中特定值的出现次数、对全部元素求和、计算平均值以及确定最大值或最小值。
To sum an array A with n elements (indices 0 to n-1): initialise total ← 0, then FOR i ← 0 TO n-1, total ← total + A[i], ENDFOR. The algorithm uses an accumulator variable.
对含有n个元素的数组A（索引0到n-1）求和：初始化total ← 0，然后FOR i ← 0 TO n-1，total ← total + A[i]，ENDFOR。该算法使用了累加器变量。
To count how many times the value 7 appears in a list: set count ← 0, iterate through every element, and if the current element equals 7, increment count. The final count is the answer.
要统计数值7在列表中出现的次数：设置count ← 0，遍历每个元素，当当前元素等于7时增加count。最终的count即为答案。
Finding the maximum follows a similar pattern: initialise max ← first element, then for every remaining element, if the element > max, update max ← element. This pattern can be adapted for minimum by reversing the comparison.
寻找最大值遵循类似模式：初始化max ← 第一个元素，然后对于每个剩余元素，如果当前元素大于max，则更新max ← 当前元素。可通过反转比较方向来寻找最小值。
5. Searching Algorithms: Linear Search & Binary Search | 搜索算法：线性查找与二分查找
Linear search examines each item in a list one by one until the target is found or the end is reached. It does not require the data to be sorted and works on any list. Its time complexity is O(n) in the worst case, as it may need to check all n elements.
线性查找逐个检查列表中的每一项，直到找到目标或到达列表末尾。它不要求数据有序，适用于任何列表。其最坏情况时间复杂度为O(n)，因为它可能需要检查全部n个元素。
Binary search is a much more efficient algorithm but demands that the list is already sorted. It repeatedly compares the target with the middle element: if they match, the search ends; if the target is smaller, the search continues on the left half; if larger, on the right half. Each comparison halves the search space, yielding O(log n) complexity.
二分查找效率高得多，但要求列表已经排序。它反复将目标与中间元素比较：若匹配，搜索结束；若目标更小，则在左半部分继续搜索；若更大，则在右半部分继续。每次比较都将搜索空间减半，因此复杂度为O(log n)。
A typical binary search pseudocode initialises low ← 0 and high ← n-1, then WHILE low ≤ high: mid ← high based on comparison. If the loop ends without finding the target, it is not present.
典型的二分查找伪代码初始化low ← 0和high ← n-1，然后WHILE low ≤ high：mid ← (low + high) DIV 2，再根据比较结果调整low或high。如果循环结束未找到目标，则目标不存在。
6. Sorting Algorithms: Bubble Sort & Insertion Sort | 排序算法：冒泡排序与插入排序
Bubble sort works by repeatedly stepping through the list, comparing adjacent elements and swapping them if they are in the wrong order. With each full pass, the largest unsorted element 'bubbles' to its correct position at the end. The process repeats for the remaining unsorted portion.
冒泡排序通过反复遍历列表，比较相邻元素并在顺序错误时交换它们。每完成一趟完整扫描，当前未排序部分中最大的元素就会"冒泡"到其正确的位置末端。这一过程对剩余未排序部分重复进行。
The algorithm requires n-1 passes in the worst case, and each pass examines up to n-1 pairs. This results in O(n²) time complexity. A flag can be used to detect if any swaps occurred in a pass; if none, the list is already sorted and the algorithm can terminate early.
该算法在最坏情况下需要n-1趟扫描，每趟最多检查n-1对元素，因此时间复杂度为O(n²)。可以使用一个标志位来检测某趟是否发生了交换；如果没有，则列表已经有序，算法可以提前终止。
Insertion sort builds the final sorted list one item at a time. It assumes the first element is trivially sorted, then takes the next element and inserts it into its correct position among the previously sorted elements, shifting larger elements to the right as needed. It resembles how you might sort playing cards in your hand.
插入排序每次一项地构建最终有序列表。它假定第一个元素已经排好序，然后取下一个元素，将其插入到前面已排序部分中的正确位置，必要时将较大元素向右移动。这类似于你手中整理扑克牌的方式。
Insertion sort has O(n²) average and worst-case complexity but is O(n) if the data is already mostly sorted. It is often more efficient than bubble sort in practice, especially for small datasets.
插入排序的平均和最坏情况复杂度为O(n²)，但在数据基本有序时为O(n)。在实践中它通常比冒泡排序效率更高，尤其对于小型数据集。
7. Advanced Sorting: Merge Sort & Quick Sort Overview | 高级排序：归并排序与快速排序概述
Merge sort is a divide-and-conquer algorithm. It recursively splits the unsorted list into two halves until each sublist contains one element (which is inherently sorted). Then it repeatedly merges sorted sublists to produce new sorted sublists until the entire list is reconstructed in order. Its time complexity is O(n log n) in all cases, but it requires additional memory for the merging process.
归并排序是一种分治算法。它递归地将未排序列表分成两半，直到每个子列表只含一个元素（本身已排序）。然后它反复将有序子列表合并成新的有序子列表，直至整个列表被按序重建。其时间复杂度在所有情况下均为O(n log n)，但合并过程需要额外内存空间。
Quick sort also uses divide and conquer. It selects a 'pivot' element from the list and partitions the other elements into two sublists: those less than the pivot and those greater than the pivot. The sublists are then recursively sorted. The average time complexity is O(n log n), but if poor pivots are chosen (e.g., always the smallest element), the worst case degrades to O(n²). Randomised pivot selection can mitigate this.
快速排序也采用分治法。它从
Published by TutorHao | IB Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图