📚 Searching and Sorting Algorithms for Edexcel A-Level Programming | Edexcel A-Level 编程中的搜索与排序算法
Searching and sorting algorithms are central to Edexcel A-Level Computer Science, especially in Paper 2: Thinking Logically and Algorithms. This article explains the key algorithms, traces their behaviour and compares their Big O complexity so you can answer exam questions confidently.
搜索与排序算法是 Edexcel A-Level 计算机科学的核心内容，尤其是在 Paper 2：逻辑思维与算法中。本文解释关键算法、跟踪其行为并比较它们的大 O 复杂度，帮助你自信地应对考试题目。
1. Algorithms and Computational Thinking | 算法与计算思维
An algorithm is a finite sequence of well-defined instructions that produces a result for a given input. In Edexcel A-Level Programming, computational thinking includes abstraction, decomposition, pattern recognition and algorithmic reasoning.
算法是有限且定义明确的指令序列，可针对给定输入产生结果。在 Edexcel A-Level 编程中，计算思维包括抽象、分解、模式识别和算法推理。
Every algorithm must have clear inputs, outputs, processing steps and a terminating condition. Without these properties, a program may loop forever or produce incorrect results.
每个算法都必须有清晰的输入、输出、处理步骤和终止条件。缺少这些性质，程序可能无限循环或产生错误结果。
- Input: data provided to the algorithm before execution.
- Output: the result produced after processing.
- Definiteness: every step is clear and unambiguous.
- Finiteness: the algorithm terminates after a finite number of steps.
- Effectiveness: each step is basic enough to be carried out in practice.
输入：执行前提供给算法的数据；输出：处理后产生的结果；确定性：每一步都清晰无歧义；有限性：算法在有限步后终止；有效性：每一步都足够基本，可以实际执行。
2. Linear Search | 线性搜索
Linear search checks each item in a list one by one until the target value is found or the end is reached. It works on both sorted and unsorted data, which makes it flexible but often slow for large lists.
线性搜索逐一检查列表中的每个元素，直到找到目标值或到达列表末尾。它适用于已排序和未排序数据，因此灵活但在大列表中通常较慢。
The algorithm begins at index 0 and compares the target with each element. If a match is found, it returns the index; otherwise, it continues to the next element.
该算法从索引 0 开始，将目标与每个元素比较。如果找到匹配项，返回索引；否则继续检查下一个元素。
In the worst case, the target is not present and every element must be examined. The time complexity is therefore O(n).
在最坏情况下，目标不存在，必须检查每个元素。因此时间复杂度为 O(n)。
- Best case: target found at position 0 — O(1)
- Average case: target found near the middle — O(n/2), simplified to O(n)
- Worst case: target not found — O(n)
最好情况：目标在第 0 位找到 — O(1)；平均情况：目标在中间附近找到 — O(n/2)，简化为 O(n)；最坏情况：目标不存在 — O(n)。
3. Binary Search | 二分搜索
Binary search repeatedly divides a sorted list in half. It compares the middle element with the target and discards the half that cannot contain the target.
二分搜索反复将已排序列表分成两半。它比较中间元素与目标值，并舍弃不可能包含目标的那一半。
The middle index is calculated using the low and high boundaries:
中间索引使用下界和上界计算：
mid = low + (high − low) ÷ 2
This avoids integer overflow and gives the same result as (low + high) ÷ 2 in normal cases. Binary search runs in O(log₂ n) time.
这避免了整数溢出，在正常情况下与 (low + high) ÷ 2 结果相同。二分搜索的时间复杂度为 O(log₂ n)。
It is essential to remember that binary search only works on sorted data. Applying it to an unsorted list gives meaningless results.
必须记住二分搜索只适用于已排序数据。对未排序列表使用二分搜索会得到无意义的结果。
4. Comparing Search Algorithms | 搜索算法对比
Linear search is simple and requires no ordering, but binary search is much faster when the data is sorted. The trade-off is the cost of sorting plus the need for random access.
线性搜索简单且不需要排序，但数据已排序时二分搜索快得多。代价是排序成本以及需要随机访问。
| Criterion | Linear Search | Binary Search |
|---|---|---|
| Precondition | None | Sorted data |
| Worst-case time | O(n) | O(log₂ n) |
| Space | O(1) | O(1) |
对于小数据集，线性搜索是可接受的；对于大数据集且已排序，二分搜索显著减少比较次数。
5. Bubble Sort | 冒泡排序
Bubble sort works by repeatedly comparing adjacent elements and swapping them if they are in the wrong order. After each pass, the largest unsorted element bubbles to its final position at the end.
冒泡排序通过反复比较相邻元素并在顺序错误时交换来工作。每一轮后，最大的未排序元素“冒泡”到末尾的最终位置。
If a full pass makes no swaps, the list is already sorted and the algorithm can stop early. This optimised version has best-case O(n).
如果一整轮没有发生交换，说明列表已经有序，算法可以提前停止。这种优化版本的最好情况为 O(n)。
- Worst-case time: O(n²)
- Average-case time: O(n²)
- Best-case time: O(n) with early exit
- Space: O(1) — in-place
最坏情况时间：O(n²)；平均情况时间：O(n²)；最好情况时间：O(n)（使用提前退出）；空间：O(1) — 原地排序。
6. Insertion Sort | 插入排序
Insertion sort builds a sorted sublist one element at a time by inserting each new element into its correct position among the previously sorted items.
插入排序通过将每个新元素插入已排序元素中的正确位置，一次构建一个有序子列表。
It is stable and efficient for small or nearly sorted data, with best-case O(n) and worst-case O(n²).
它是稳定的，适用于小规模或近乎有序的数据，最好情况 O(n)，最坏情况 O(n²)。
This algorithm is often used in practice as a finishing step for more complex sorts or when the list is already almost sorted.
该算法在实践中常被用作更复杂排序的收尾步骤，或当列表已经几乎有序时使用。
7. Merge Sort | 归并排序
Merge sort is a divide-and-conquer algorithm. It recursively splits the list into halves until each sublist has length 1, then repeatedly merges sorted sublists to produce new sorted lists.
归并排序是一种分治算法。它递归地将列表分成两半，直到每个子列表长度为 1，然后反复合并且已排序的子列表以产生新的有序列表。
Merge sort guarantees O(n log₂ n) time in all cases, but it needs O(n) extra space for the temporary arrays used during merging.
归并排序在所有情况下都保证 O(n log₂ n) 时间，但在合并过程中需要 O(n) 额外空间用于临时数组。
Its stable nature and consistent performance make it a good choice when memory is not a major constraint.
它的稳定性和一致的性能使其在内存不是主要限制时成为良好选择。
8. Quick Sort | 快速排序
Quick sort also uses divide and conquer. It selects a pivot, partitions the array so that elements smaller than the pivot come before it and larger elements after it, then recursively sorts the two partitions.
快速排序也使用分治法。它选择一个基准值，对数组进行分区，使小于基准的元素在其前，大于基准的元素在其后，然后递归排序两个分区。
Average-case time is O(n log₂ n), but the worst case is O(n²) when poor pivot choices lead to highly unbalanced partitions.
平均情况时间为 O(n log₂ n)，但当基准选择不当导致分区高度不平衡时，最坏情况为 O(n²)。
Quick sort is often in-place and requires only O(log₂ n) average space for recursion, making it faster in many practical situations.
快速排序通常是原地排序，平均仅需要 O(log₂ n) 递归空间，因此在许多实际情况下速度更快。
9. Big O Notation and Complexity | 大 O 表示法与复杂度
Big O notation describes an upper bound on the growth rate of an algorithm’s time or space requirements. It ignores constants and lower-order terms because they matter little for large n.
大 O 表示法描述了算法时间或空间需求增长率的上界。它忽略常数和低阶项，因为当 n 很大时它们影响很小。
| Complexity | Example |
|---|---|
| O(1) | Hash table lookup, direct array access |
| O(log₂ n) | Binary search |
| O(n) | Linear search |
| O(n log₂ n) | Merge sort, quick sort average case |
| O(n²) | Bubble sort, insertion sort worst case |
考试常要求根据代码或伪代码判断复杂度，并比较不同算法的可扩展性。
10. Choosing the Right Algorithm | 选择正确的算法
The best algorithm depends on data size, whether the data is sorted, memory limits, stability requirements and implementation effort. For example, binary search is only justified if sorting is already done or search frequency is high.
Published by TutorHao | A-Level 编程 Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导