Sorting and Searching Algorithms for A-Level Programming | A-Level 编程中的排序与搜索算法

📚 Sorting and Searching Algorithms for A-Level Programming | A-Level 编程中的排序与搜索算法

Algorithms are the heart of programming. At A-Level, you must be able to design, trace, and compare standard searching and sorting algorithms, and understand their efficiency using Big-O notation.

算法是编程的核心。在 A-Level 阶段，你必须能够设计、追踪和比较标准的搜索与排序算法，并使用大 O 表示法理解它们的效率。

1. Computational Thinking and Algorithm Design | 计算思维与算法设计

Computational thinking involves breaking a problem into manageable parts, identifying patterns and abstractions, and designing a step-by-step algorithm to solve it. An algorithm is a precise sequence of instructions that terminates with a result.

计算思维包括把问题分解为可处理的部分、识别模式与抽象，并设计逐步执行的算法来解决问题。算法是终止并产生结果的精确指令序列。

Key stages of computational thinking include:

计算思维的关键阶段包括：

Decomposition – breaking down a problem into smaller sub-problems – 分解 – 将问题拆分为更小的子问题
Pattern recognition – identifying similarities with known problems – 模式识别 – 识别与已知问题的相似性
Abstraction – filtering out irrelevant detail – 抽象 – 过滤掉无关细节
Algorithm design – writing the exact steps to solve the problem – 算法设计 – 编写解决问题的确切步骤

2. Linear Search | 线性搜索

A linear search checks each element of a list in turn until the target is found or the end is reached. It works on unsorted data but is slow for large lists.

线性搜索逐个检查列表中的每个元素，直到找到目标或到达列表末尾。它适用于未排序的数据，但对大列表速度较慢。

FOR i ← 0 TO n-1
IF arr[i] = target THEN
RETURN i
END IF
NEXT i
RETURN -1

The worst-case time complexity is O(n), because every element may need to be checked. The best case is O(1) when the target is the first element.

最坏情况的时间复杂度是 O(n)，因为可能需要检查每个元素。最佳情况是 O(1)，当目标是第一个元素时。

3. Binary Search | 二分搜索

Binary search is a divide-and-conquer algorithm that repeatedly halves the search interval. It requires the list to be sorted before searching.

二分搜索是一种分治算法，它不断将搜索区间减半。它要求列表在搜索前已经排序。

low ← 0
high ← n-1
WHILE low ≤ high DO
  mid ← (low + high) DIV 2
  IF arr[mid] = target THEN RETURN mid
  ELSE IF arr[mid] < target THEN low ← mid + 1
  ELSE high ← mid – 1
END WHILE
RETURN -1

Each comparison halves the search space, so the time complexity is O(log n). This makes binary search far more efficient than linear search for large sorted datasets.

每次比较都会使搜索空间减半，因此时间复杂度为 O(log n)。这使得二分搜索在大规模已排序数据集上远比线性搜索高效。

4. Bubble Sort | 冒泡排序

Bubble sort repeatedly steps through a list, compares adjacent elements, and swaps them if they are in the wrong order. The largest unsorted element bubbles to its correct position after each pass.

冒泡排序反复遍历列表，比较相邻元素，如果顺序错误则交换它们。每经过一轮，最大的未排序元素就会冒泡到正确的位置。

FOR i ← 0 TO n-2
  FOR j ← 0 TO n-i-2
    IF arr[j] > arr[j+1] THEN
      SWAP arr[j], arr[j+1]
    END IF
  NEXT j
NEXT i

The average and worst-case complexity is O(n²) because of the nested loops. A small optimisation can stop early if no swaps are made, giving best case O(n).

由于嵌套循环，平均和最坏情况复杂度为 O(n²)。如果增加优化，在没有交换时提前停止，最佳情况可达到 O(n)。

5. Insertion Sort | 插入排序

Insertion sort builds a sorted portion one element at a time. It takes each new element and inserts it into its correct position within the already sorted part of the list.

插入排序一次一个元素地构建已排序部分。它取出每个新元素，并将其插入到列表中已排序部分的正确位置。

FOR i ← 1 TO n-1
  key ← arr[i]
  j ← i – 1
  WHILE j ≥ 0 AND arr[j] > key DO
    arr[j+1] ← arr[j]
    j ← j – 1
  END WHILE
  arr[j+1] ← key
NEXT i

Insertion sort is O(n²) in the worst case but is particularly efficient for small or nearly sorted lists. It is stable and works well online, sorting items as they arrive.

插入排序在最坏情况下为 O(n²)，但对小型或接近排序的列表特别高效。它是稳定的，并且适合在线排序，即数据到达时立即处理。

6. Merge Sort | 归并排序

Merge sort is a classic divide-and-conquer algorithm. It splits the list into halves, recursively sorts each half, and then merges the two sorted halves back together.

归并排序是一种经典的分治算法。它将列表分成两半，递归地对每一半排序，然后将两个已排序的部分合并在一起。

FUNCTION mergeSort(arr)
  IF LEN(arr) ≤ 1 THEN RETURN arr
  mid ← LEN(arr) DIV 2
  left ← mergeSort(arr[0..mid-1])
  right ← mergeSort(arr[mid..LEN(arr)-1])
  RETURN merge(left, right)
END FUNCTION

Merge sort has a guaranteed time complexity of O(n log n) in all cases, making it very reliable for large datasets. However, it requires extra memory of O(n) for the merging process.

归并排序在所有情况下都能保证 O(n log n) 的时间复杂度，这使得它对大型数据集非常可靠。然而，合并过程需要 O(n) 的额外内存。

7. Big-O Notation and Efficiency | 大 O 表示法与效率

Big-O notation describes how the running time or memory usage of an algorithm grows as the input size n increases. It focuses on the dominant term and ignores constant factors.

大 O 表示法描述算法的运行时间或内存使用随输入规模 n 增长的情况。它关注主导项，并忽略常数因子。

Complexity	Name	Example
O(1)	Constant	Array index access
O(log n)	Logarithmic	Binary search
O(n)	Linear	Linear search
O(n log n)	Linearithmic	Merge sort
O(n²)	Quadratic	Bubble sort, insertion sort
O(2ⁿ)	Exponential	Recursive Fibonacci without memoisation

In Edexcel exams, you are expected to identify the best, worst, and average case complexities of standard algorithms and to compare their suitability for different data sizes.

在 Edexcel 考试中，你需要识别标准算法的最佳、最坏和平均情况复杂度，并比较它们对不同数据规模的适用性。

8. Recursion in Programming | 编程中的递归

Recursion is a technique where a function calls itself to solve smaller instances of the same problem. Every recursive algorithm must have a base case to stop the recursion and a recursive step that reduces the problem size.

递归是一种函数调用自身来解决更小规模同类问题的技术。每个递归算法必须有一个基准情形来停止递归，以及一个减少问题规模的递归步骤。

The factorial function is a standard example:

阶乘函数是一个标准示例：

factorial(n) = 1 IF n = 0
factorial(n) = n × factorial(n-1) IF n > 0

Recursive solutions can be elegant but may use more memory because each call is stored on the call stack. Iterative solutions are often more efficient for simple problems.

递归解决方案可能很优雅，但可能使用更多内存，因为每次调用都存储在调用栈中。对于简单问题，迭代解决方案通常更高效。

9. Stacks and Queues in Algorithms | 算法中的栈与队列

Stacks and queues are abstract data types that play a key role in implementing algorithms. A stack follows Last In, First Out (LIFO), while a queue follows First In, First Out (FIFO).

栈和队列是抽象数据类型，在实现算法中起着关键作用。栈遵循后进先出（LIFO），而队列遵循先进先出（FIFO）。

Depth-first search uses a stack to remember the path – 深度优先搜索使用栈来记住路径
Breadth-first search uses a queue to explore level by level – 广度优先搜索使用队列逐层探索
Function calls in recursion are stored on the system stack – 递归中的函数调用存储在系统栈上
Operating systems use queues for scheduling tasks – 操作系统使用队列调度任务

10. Exam Tips for Edexcel Programming Questions | Edexcel 编程题考试技巧

When answering Edexcel programming questions, always show your working by using trace tables. Trace tables help you track variable values and prove that your algorithm works for a given input.

在回答 Edexcel 编程题时，一定要通过使用追踪表展示你的推理过程。追踪表帮助你跟踪变量值，并证明你的算法对给定输入有效。

Use the Edexcel pseudocode style consistently, with clear indentation and correct keywords such as FOR, WHILE, IF, THEN, ELSE, END IF, and RETURN. If you use a different language, state your language clearly.

一致地使用 Edexcel 伪代码风格，具有清晰的缩进和正确的关键字，如 FOR、WHILE、IF、THEN、ELSE、END IF 和 RETURN。如果你使用其他语言，请清楚地说明你使用的语言。

Always state the time complexity of your algorithm and justify it using the structure of the code. For example, a single loop gives O(n), while two nested loops give O(n²).

始终陈述你的算法的时间复杂度，并使用代码结构进行论证。例如，单个循环得到 O(n)，而两个嵌套循环得到 O(n²)。

Finally, test your algorithm with boundary cases such as an empty list, a single-element list, and a list where the target is the first or last element.

最后，使用边界情况测试你的算法，比如空列表、单元素列表以及目标在第一个或最后一个位置的情况。

Published by TutorHao | Programming Revision Series | aleveler.com

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

Sorting and Searching Algorithms for A-Level Programming | A-Level 编程中的排序与搜索算法