GCSE OCR Computer Science: Algorithms | GCSE OCR 计算机：算法考点精讲

📚 GCSE OCR Computer Science: Algorithms | GCSE OCR 计算机：算法考点精讲

Algorithms are the fundamental building blocks of computer programs. In the GCSE OCR Computer Science course, understanding how to design, analyse and compare algorithms is essential for both exam success and real-world problem solving. This article provides a comprehensive breakdown of every key concept, from computational thinking to searching and sorting algorithms, with bilingual explanations to reinforce your learning.

算法是计算机程序的基本构件。在 GCSE OCR 计算机科学课程中，理解如何设计、分析和比较算法对考试成功和解决实际问题都至关重要。本文全面拆解每一个核心概念，从计算思维到搜索与排序算法，配以中英双语讲解，帮助你加深理解。

1. What is an Algorithm? | 什么是算法？

An algorithm is a step-by-step set of instructions designed to solve a specific problem or perform a task. It must be precise, unambiguous and finite – meaning it always terminates after a certain number of steps. Algorithms can be expressed in natural language, pseudocode or flowcharts, and they form the logic behind everything from search engines to video games.

算法是一组为了完成特定任务或解决某个问题而设计的逐步指令。它必须精确、无歧义且有穷性 —— 也就是说，算法总会在有限步骤后结束。算法可以用自然语言、伪代码或流程图表达，它是从搜索引擎到电子游戏各类程序背后的逻辑基础。

For example, a simple algorithm to make a cup of tea includes steps like ‘boil water’, ‘add tea bag to cup’, ‘pour water into cup’, ‘wait for 3 minutes’, ‘remove tea bag’. Each step is clear and ordered. In computing, we write algorithms to manipulate data, search for items or sort lists – always aiming for correctness and efficiency.

例如，一个制作一杯茶的简单算法包括这些步骤：“烧水”、“将茶包放入杯中”、“将水倒入杯中”、“等待3分钟”、“取出茶包”。每一步都清晰有序。在计算领域，我们编写算法来处理数据、查找项目或对列表排序 —— 始终追求正确性与效率。

2. Computational Thinking Principles | 计算思维原则

Decomposition involves breaking a complex problem into smaller, more manageable parts. By tackling each sub-problem individually, you reduce complexity and can solve the overall problem more efficiently. For instance, developing a mobile app can be decomposed into designing the user interface, writing backend logic and testing.

分解是将一个复杂问题拆分成更小、更易管理的部分。通过逐一处理每个子问题，可以降低复杂度，从而更有效地解决整个问题。例如，开发一个手机应用可以分解为设计用户界面、编写后端逻辑和测试。

Abstraction is about focusing on the essential details and ignoring irrelevant information. It allows you to create models that represent reality without unnecessary complexity. A map of the London Underground is a classic abstract model: it shows station connections but omits precise geographical distances.

抽象是指关注关键细节而忽略无关信息。它让你能够建立代表现实的模型，同时避免不必要的复杂性。伦敦地铁图就是一个经典的抽象模型：它展示了车站间的连接，却省略了精确的地理距离。

Pattern recognition identifies similarities or trends in problems to apply known solutions. If you have successfully solved a sorting problem before, recognising that a new challenge involves ordering data allows you to reuse the same algorithm. This speeds up problem solving and reduces errors.

模式识别 是指发现问题中的相似性或趋势，以便应用已知的解决方案。如果你以前成功解决过排序问题，发现一个新挑战也涉及数据排序，就可以复用相同的算法。这能加快问题解决过程并减少错误。

Algorithmic thinking is the process of formulating a step-by-step solution that can be carried out by a computer. It requires logical reasoning and the ability to turn a high-level idea into precise instructions. This principle underpins the design of every program you write.

算法思维 是制定能够由计算机执行的逐步解决方案的过程。它需要逻辑推理能力，以及将高层次想法转化为精确指令的能力。这一原则是编写每个程序的基础。

3. Representing Algorithms: Pseudocode and Flowcharts | 算法表示：伪代码与流程图

Algorithms must be communicated clearly. In the OCR exam, you need to read, write and trace algorithms in both pseudocode and flowcharts. Pseudocode uses English-like statements with consistent keywords such as SET, IF...THEN...ELSE, FOR...ENDFOR and WHILE...ENDWHILE. It avoids strict syntax rules, making it accessible for planning.

算法必须清晰地表达出来。在 OCR 考试中，你需要能够阅读、编写并用伪代码和流程图追踪算法。伪代码使用类似英语的语句和一致的关键词，如 SET、IF...THEN...ELSE、FOR...ENDFOR 和 WHILE...ENDWHILE。它避开了严格的语法规则，易于用于规划。

Flowcharts use standard symbols to show the flow of logic.

流程图使用标准符号来表示逻辑流程。

Symbol	Meaning
Oval	Start / End
Rectangle	Process (e.g. calculation)
Parallelogram	Input / Output
Diamond	Decision (Boolean condition)
Arrow	Flow direction

符号	含义
椭圆形	开始 / 结束
矩形	处理（例如计算）
平行四边形	输入 / 输出
菱形	判定（布尔条件）
箭头	流程方向

When tracing a flowchart, you follow the arrows and update values as directed. In the exam, you may be asked to complete a trace table or identify the output for given inputs. Always read decision diamonds carefully – they determine which path the algorithm takes next.

追踪流程图时，你沿着箭头方向并根据指示更新数值。考试中可能要求你填写追踪表或给出特定输入的输出。务必仔细阅读判定菱形 —— 它们决定了算法下一步走哪条路径。

4. Linear Search | 线性搜索

Linear search is the simplest searching algorithm. It checks each element of a list one by one until the target is found or the end of the list is reached. This algorithm works on both unsorted and sorted lists and is easy to implement.

线性搜索是最简单的搜索算法。它逐一检查列表中的每个元素，直到找到目标或到达列表末尾。该算法适用于无序和有序列表，实现简单。

The pseudocode for linear search can be written as:

SET found TO False
FOR index FROM 0 TO length(list) - 1
    IF list[index] = target THEN
        OUTPUT index
        SET found TO True
        BREAK
    ENDIF
ENDFOR
IF NOT found THEN
    OUTPUT "Not found"
ENDIF

中文解释：线性搜索的伪代码如下：首先设置 found 为假。从索引 0 到列表长度减1逐一比较，若找到则输出索引并置 found 为真后立即跳出循环。若循环结束仍未找到，则输出“Not found”。

Performance: In the worst case, linear search must examine every element. For a list of size n, the maximum number of comparisons is n. This is considered slow for large data sets, but it is the only option when the list is not sorted.

性能：在最坏情况下，线性搜索需检查每个元素。对于大小为 n 的列表，最大比较次数为 n。对大数据集而言这很慢，但当列表未排序时，这是唯一的选择。

5. Binary Search | 二分搜索

Binary search is a much faster algorithm but requires the list to be sorted in ascending (or descending) order. It repeatedly divides the search interval in half, eliminating half the remaining elements each time. This ‘divide and conquer’ approach drastically reduces the number of comparisons needed.

二分搜索快得多，但要求列表按升序（或降序）排列。它反复将搜索区间一分为二，每次排除剩余元素的一半。这种“分而治之”的方法大幅减少了所需的比较次数。

Algorithm steps: 1. Set low to 0 and high to length-1. 2. While low ≤ high, calculate mid = (low + high) // 2. 3. If list[mid] equals the target, return mid. 4. If list[mid] < target, set low = mid + 1. 5. Else (list[mid] > target), set high = mid – 1. 6. If the loop ends without return, the target is not in the list.

算法步骤：1. 将 low 设为 0，high 设为长度减1。2. 当 low ≤ high 时，计算 mid = (low + high) // 2。3. 若 list[mid] 等于目标值，返回 mid。4. 若 list[mid] < 目标值，令 low = mid + 1。5. 否则（list[mid] > 目标值），令 high = mid – 1。6. 循环结束仍未返回，则目标不在列表中。

Example: Searching for 23 in [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]: low=0, high=9, mid=4 (value 16) -> 23>16 so low=5; mid=7 (56) -> 23<56 so high=6; mid=5 (23) -> found at index 5.

示例：在 [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] 中搜索 23：low=0, high=9, mid=4（值为16）-> 23>16，故 low=5；mid=7 (56) -> 23<56，故 high=6；mid=5 (23) -> 在索引5处找到。

Performance: The worst-case number of comparisons is approximately log₂(n). For a list of 1,000 elements, binary search needs at most about 10 comparisons, whereas linear search could need 1,000. Binary search is therefore extremely efficient for large sorted datasets.

性能：最坏情况下的比较次数大约为 log₂(n)。对于包含 1,000 个元素的列表，二分搜索最多需要约 10 次比较，而线性搜索可能需要 1,000 次。因此对于大型有序数据集，二分搜索极其高效。

6. Bubble Sort | 冒泡排序

Bubble sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. It is named because smaller elements ‘bubble’ to the top (beginning) of the list.

冒泡排序是一种简单的排序算法，它反复遍历列表，比较相邻元素并在顺序错误时交换它们。遍历列表的过程不断重复，直到不需要交换为止，这表示列表已排好序。它因较小的元素像气泡一样“浮”到列表顶部（起始端）而得名。

Pseudocode for bubble sort (optimised with a flag):

FOR i FROM 0 TO length(list)-2
    swapped ← False
    FOR j FROM 0 TO length(list)-2-i
        IF list[j] > list[j+1] THEN
            SWAP list[j], list[j+1]
            swapped ← True
        ENDIF
    ENDFOR
    IF NOT swapped THEN
        BREAK
    ENDIF
ENDFOR

冒泡排序伪代码（带标记优化）：外层循环 i 控制轮次，内层 j 比较相邻元素，若逆序则交换。每轮后若没有交换发生，说明已有序，可以提前终止。

Unlike the basic version, the optimised bubble sort stops early if the list becomes ordered before all passes complete. The algorithm is stable and easy to understand, but its average and worst-case time require O(n²) comparisons, making it unsuitable for large lists.

与基础版本不同，优化后的冒泡排序在列表提前有序时可以停止，无需完成所有轮次。该算法是稳定的且容易理解，但其平均和最坏情况都需要 O(n²) 次比较，因此不适合大型列表。

7. Insertion Sort | 插入排序

Insertion sort builds the sorted list one element at a time by taking each new element and inserting it into its correct position relative to the already sorted part. Think of the way you would sort playing cards in your hand: you pick a card and insert it into the right place among the cards already held.

插入排序通过每次取出一个新元素并将其插入到已排序部分的正确位置，逐步构建有序列表。想象你整理手中扑克牌的方式：抽出一张牌，将其插入到手中已整理好的牌里合适的位置。

Algorithm steps: 1. Start with the second element (index 1). 2. Compare it with elements to its left. 3. Shift greater elements one position to the right. 4. Insert the element into the gap. 5. Move to the next element and repeat until the end of the list.

算法步骤：1. 从第二个元素（索引1）开始。2. 将其与左边的元素比较。3. 将比它大的元素向右移动一位。4. 把该元素插入空位。5. 移至下一个元素重复，直到列表末尾。

Insertion sort is efficient for small or nearly sorted data sets, often outperforming more complex algorithms. Its worst-case time complexity is O(n²) comparisons, but it is stable and works in-place with minimal extra memory.

插入排序对小型或几乎有序的数据集非常高效，常常优于更复杂的算法。其最坏情况时间复杂度为 O(n²) 次比较，但它是稳定的，且原地工作，所需额外内存极少。

8. Merge Sort | 合并排序

Merge sort is a divide-and-conquer algorithm that recursively splits the list into halves until each sublist contains only one element (which is trivially sorted). It then repeatedly merges the sublists to produce new sorted sublists until there is only one sorted list remaining.

合并排序是一种分治算法，它递归地将列表分成两半，直到每个子列表只含一个元素（该子列表自然有序）。然后反复合并子列表以产生新的有序子列表，直至最终只剩下一个有序列表。

Steps: 1. If the list has length 1, it is already sorted – return. 2. Divide the list into two halves. 3. Recursively apply merge sort to the left half and the right half. 4. Merge the two sorted halves by comparing the smallest elements of each and building the combined sorted list.

步骤：1. 若列表长度为 1，则已排序 —— 直接返回。2. 将列表分成两半。3. 对左半部分和右半部分递归地应用合并排序。4. 合并两个有序半部分：比较两者的最小元素，构造出合并后的有序列表。

Merge sort has a consistent time complexity of O(n log n) in all cases – best, average and worst. This makes it highly reliable for large data sets. However, it requires additional memory proportional to n for the merging process, which can be a drawback in memory-constrained environments.

合并排序在所有情况下（最好、平均、最坏）的时间复杂度均为 O(n log n)。这使其对大数据集极为可靠。然而，合并过程中需要与 n 成比例的额外内存，在内存受限的环境中这可能会是一个缺点。

9. Comparing Algorithm Efficiency | 算法效率比较

When selecting an algorithm, you must consider both time and space requirements. The table below summarises the comparison count for the standard algorithms at this level.

在选择算法时，你必须同时考虑时间和空间需求。下表总结了本阶段标准算法的比较次数。

Algorithm	Best case	Worst case
Linear Search	1	n
Binary Search	1	log₂ n
Bubble Sort	n-1 (optimised)	(n-1)+(n-2)+…+1 ≈ n²/2
Insertion Sort	n-1	≈ n²/2
Merge Sort	n log n	n log n

算法	最好情况	最坏情况
线性搜索	1	n
二分搜索	1	log₂ n
冒泡排序	n-1（优化后）	(n-1)+(n-2)+…+1 ≈ n²/2
插入排序	n-1	≈ n²/2
合并排序	n log n	n log n

For GCSE, you are not required to use formal Big O notation in answers, but understanding the growth rate is key. Linear search and the quadratic sorts become extremely slow for large n, while binary search and merge sort scale much better. Remember that the best choice often depends on whether the data is already sorted or nearly sorted.

在 GCSE 阶段，你不需要在答案中使用正式的大 O 表示法，但理解增长速率是关键。线性搜索和平方级排序对于大 n 会非常慢，而二分搜索和合并排序则扩展性好得多。记住，最佳选择往往取决于数据是否已排序或接近有序。

10. Exam Tips and Common Mistakes | 考试技巧与常见错误

Trace carefully: When completing trace tables, update each variable row by row. Do not jump ahead – many marks are lost by missing intermediate values. Use a pencil and check your work against the algorithm step by step.

仔细追踪： 在完成追踪表时，要逐行更新每个变量。不要跳跃 — 很多失误都是因为遗漏了中间值。用铅笔操作，并逐步对照算法进行检查。

Know the preconditions: Binary search requires a sorted list. If a question asks you to apply binary search to an unsorted list, you must state that it will give incorrect results. Similarly, optimised bubble sort stops early only if a pass makes no swaps.

搞清前提条件： 二分搜索要求列表已排序。若题目让你对无序列表应用二分搜索，你必须指出结果会出错。同样，优化后的冒泡排序仅当某一轮没有发生交换时才会提前停止。

Pseudocode syntax: Use consistent indentation and capitalised keywords exactly as taught (SET, IF…THEN, FOR, WHILE, OUTPUT). OCR examiners expect clear, logical structure even if minor syntax variations are acceptable. Avoid mixture of programming languages.

伪代码语法： 使用一致的缩进和大写关键词，完全按照所教形式（SET、

Published by TutorHao | GCSE Computer Science Revision Series | aleveler.com

更多咨询请联系16621398022（同微信）

GCSE OCR Computer Science: Algorithms | GCSE OCR 计算机：算法考点精讲