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

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

Searching and sorting algorithms are fundamental to the Edexcel A-Level Programming specification. They appear in Paper 1 as algorithm-tracing questions, in Paper 2 as extended programming tasks, and in multiple-choice questions that test your understanding of efficiency, correctness and data structures. A strong grasp of these algorithms will help you reason about code, compare design choices and write clear pseudocode under time pressure.

搜索和排序算法是 Edexcel A-Level 编程考试的核心内容。它们会出现在 Paper 1 的算法追踪题、Paper 2 的扩展编程题，以及考查效率、正确性和数据结构的选择题中。扎实掌握这些算法能帮助你推理代码、比较设计选择，并在限时考试中写出清晰的伪代码。

---

1. Why Searching and Sorting Matter | 为什么搜索和排序很重要

Searching is the process of locating a target value in a data structure, while sorting rearranges data into a defined order, usually ascending or descending. In the Edexcel specification, you are expected to understand how standard algorithms work, their time and space complexity, and the situations in which one algorithm may be preferred over another.

搜索是在数据结构中定位目标值的过程，而排序是将数据按定义好的顺序重新排列，通常是升序或降序。Edexcel 大纲要求你理解标准算法的工作原理、时间和空间复杂度，以及在什么情况下应优先选择某一种算法。

Efficiency is not an abstract idea in exams: a linear search may be fine for a list of 20 items, but a list of 20 million items needs a very different approach. Sorting is equally important because many efficient search algorithms, such as binary search, only work on sorted data.

效率在考试中并不是抽象概念：线性搜索对 20 个元素的列表可能没有问题，但包含 2000 万个元素的列表就需要完全不同的方法。排序同样重要，因为许多高效搜索算法（如二分搜索）只能在已排序的数据上工作。

---

2. Linear Search: A Simple Scan | 线性搜索：简单扫描

Linear search, also called sequential search, checks each element in turn from the first index to the last. The algorithm stops when the target is found or when the end of the collection is reached.

线性搜索也叫顺序搜索，从第一个索引开始依次检查每个元素。当找到目标值或到达集合末尾时算法停止。

For an array of n elements, the worst case occurs when the target is not present at all: the algorithm must examine all n items. The best case occurs when the target is at the first position, requiring only one comparison.

对于包含 n 个元素的数组，最坏情况发生在目标值完全不存在时：算法必须检查全部 n 个元素。最好情况发生在目标值位于第一个位置时，只需要一次比较。

• Best case: O(1) – target is the first item. | 最好情况：O(1) – 目标值是第一个元素。

• Average case: O(n) – target is somewhere in the middle. | 平均情况：O(n) – 目标值在中间某个位置。

• Worst case: O(n) – target is not present. | 最坏情况：O(n) – 目标值不存在。

Linear search works on both sorted and unsorted data, and it uses only a constant amount of extra memory. Its simplicity makes it a good baseline for comparing other algorithms.

线性搜索既适用于已排序数据，也适用于未排序数据，而且只使用常量级别的额外内存。它的简单性使其成为比较其他算法的良好基准。

---

3. Binary Search: Divide and Conquer | 二分搜索：分而治之

Binary search only works on a sorted array. It repeatedly compares the target value with the middle element of the current search range and discards the half that cannot contain the target.

二分搜索只适用于已排序数组。它反复将目标值与当前搜索范围的中间元素进行比较，并丢弃不可能包含目标值的那一半。

If the middle element is greater than the target, the search continues in the lower half. If the middle element is smaller than the target, the search continues in the upper half. Each comparison reduces the search space by roughly 50%.

如果中间元素大于目标值，就在较小的一半继续搜索。如果中间元素小于目标值，就在较大的一半继续搜索。每次比较都会将搜索空间减少约 50%。

The number of steps required is therefore approximately log₂ n. This is an enormous improvement over linear search for large collections: for a million items, binary search needs only about 20 comparisons in the worst case, while linear search may need a million.

因此所需步数约为 log₂ n。对于大型集合，这比线性搜索有巨大改进：对于一百万个元素，二分搜索最坏情况下只需要约 20 次比较，而线性搜索可能需要一百万次。

However, binary search requires sorted data, and if the data is not already sorted, the cost of sorting must also be considered. The algorithm can be written iteratively or recursively; both versions have O(1) auxiliary space for the iterative form and O(log₂ n) call stack space for the recursive form.

但是二分搜索要求数据已排序，如果数据尚未排序，还必须考虑排序成本。该算法可以写成迭代或递归形式；迭代形式使用 O(1) 辅助空间，递归形式使用 O(log₂ n) 调用栈空间。

---

4. Comparing Search Efficiency | 搜索效率比较

Exam questions often ask you to justify why one search algorithm is more suitable than another. The table below summarises the key comparison points.

考试题目经常要求你说明为什么一种搜索算法比另一种更合适。下表总结了关键比较点。

Algorithm | 算法	Best | 最好	Average | 平均	Worst | 最坏	Sorted? | 需排序?
Linear Search | 线性搜索	O(1)	O(n)	O(n)	No | 否
Binary Search | 二分搜索	O(1)	O(log₂ n)	O(log₂ n)	Yes | 是

When the data is static and will be searched many times, sorting once and then using binary search is usually the best choice. When the data changes frequently or is very small, linear search may be simpler and fast enough.

当数据是静态的并且会被多次搜索时，先排序一次然后使用二分搜索通常是最佳选择。当数据频繁变化或规模很小时，线性搜索可能更简单且速度足够快。

---

5. Bubble Sort: The Classroom Classic | 冒泡排序：经典入门算法

Bubble sort repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. After each complete pass, the largest unsorted element ‘bubbles’ to its correct position at the end.

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

The algorithm continues making passes until no more swaps are needed. A boolean flag can be used to detect an early exit when the list becomes sorted before all n-1 passes are complete.

算法继续进行遍历，直到不再需要交换为止。可以使用布尔标志来检测列表在全部 n-1 轮遍历完成之前是否已经有序，从而提前退出。

Bubble sort is stable and operates in-place, but its worst-case and average-case time complexity are both O(n²). This makes it impractical for large datasets, though it is useful for teaching fundamental ideas such as pairwise comparison and iteration.

冒泡排序是稳定的，并且是原地排序，但其最坏情况和平均情况的时间复杂度都是 O(n²)。这使得它不适用于大型数据集，但它有助于教授成对比较和迭代等基本思想。

---

6. Insertion Sort: An Incremental Approach | 插入排序：增量方法

Insertion sort builds a sorted portion at the beginning of the list. It takes the next unsorted element and inserts it into its correct position within the sorted portion, shifting larger elements to the right as needed.

插入排序在列表开头构建已排序部分。它取出下一个未排序元素，并将其插入已排序部分的正确位置，必要时将较大的元素向右移动。

In the best case, when the input is already sorted, insertion sort only makes n-1 comparisons and no shifts, giving O(n) time. The worst case is a reverse-sorted list, where every new element must be compared with all previously sorted elements, giving O(n²).

在最好情况下，当输入已经有序时，插入排序只进行 n-1 次比较且不需要移动，时间复杂度为 O(n)。最坏情况是逆序列表，每个新元素都需要与之前所有已排序元素比较，时间复杂度为 O(n²)。

Insertion sort is stable, in-place and very efficient for small or nearly sorted datasets. Many programming libraries use insertion sort as the base case for more advanced algorithms such as merge sort and quick sort.

插入排序是稳定的、原地排序，对于小型或接近有序的数据集非常高效。许多编程库使用插入排序作为归并排序和快速排序等更高级算法的基本情形。

---

7. Merge Sort: Guaranteed O(n log n) | 归并排序：稳定的 O(n log n)

Merge sort is a divide-and-conquer algorithm. It recursively divides the array into two halves until each subarray has one element, which is trivially sorted. Then it merges the sorted halves back together by repeatedly selecting the smaller leading element.

归并排序是一种分治算法。它递归地将数组分成两半，直到每个子数组只有一个元素，而单个元素自然是有序的。然后通过反复选择较小的前导元素将有序的两半合并回去。

The merge step takes linear time, and there are log₂ n levels of recursion. The overall time complexity is therefore O(n log₂ n) in the best, average and worst cases – a significant advantage over the O(n²) sorts.

合并步骤需要线性时间，递归共有 log₂ n 层。因此最佳、平均和最坏情况下的总体时间复杂度都是 O(n log₂ n) – 相比 O(n²) 排序有显著优势。

Merge sort is stable but requires O(n) extra space for the temporary arrays used during merging. This extra memory requirement should be mentioned when justifying why an in-place algorithm might be preferred in memory-constrained environments.

归并排序是稳定的，但需要 O(n) 额外空间来存放合并过程中使用的临时数组。当需要说明为何在内存受限环境中可能优先选择原地算法时，应提及这一额外内存需求。

---

8. Quick Sort: The Pragmatic Choice | 快速排序：实用的选择

Quick sort is another divide-and-conquer algorithm. It selects a pivot element, partitions the array so that all elements less than the pivot come before it and all elements greater come after it, then recursively sorts the two partitions.

快速排序是另一种分治算法。它选择一个基准元素，将数组分区，使所有小于基准的元素位于基准之前，所有大于基准的元素位于基准之后，然后递归地对两个分区进行排序。

The average-case time complexity is O(n log₂ n), which is why quick sort is widely used in practice. However, if the pivot is consistently the smallest or largest element, the partitions are unbalanced and the worst-case time becomes O(n²).

平均情况时间复杂度为 O(n log₂ n)，这就是快速排序在实践中被广泛使用的原因。但是如果基准值始终是最小或最大元素，分区就会不平衡，最坏情况时间复杂度变为 O(n²)。

Quick sort is usually implemented in-place, so it uses O(1) extra space aside from recursion stack space, which is O(log₂ n) on average. Depending on how the partition step handles equal elements, quick sort can be stable or unstable – most basic implementations are not stable.

快速排序通常以原地方式实现，因此除递归栈空间（平均为 O(log₂ n)）外，只使用 O(1) 额外空间。根据分区步骤处理相等元素的方式不同，快速排序可以是稳定的，也可以是不稳定的 – 大多数基本实现是不稳定的。

---

9. Big-O Notation in Exams | 考试中的大 O 表示法

Big-O notation describes the upper bound of an algorithm’s growth rate as the input size n increases. It ignores constant factors and lower-order terms because they become insignificant for large n.

大 O 表示法描述算法随着输入规模 n 增大时的增长率上界。它忽略常数因子和低阶项，因为它们对于较大的 n 变得不再重要。

For example, an algorithm with 3n² + 5n + 2 operations is said to be O(n²). When comparing algorithms, focus on how the number of operations scales: O(log₂ n) is better than O(n), which is better than O(n log₂ n), which is better than O(n²).

例如，一个需要 3n² + 5n + 2 次操作的算法被称为 O(n²)。比较算法时，要关注操作次数如何增长：O(log₂ n) 优于 O(n)，O(n) 优于 O(n log₂ n)，O(n log₂ n) 优于 O(n²)。

Exam questions may ask you to calculate the number of comparisons for a specific input, identify the complexity class of a given pseudocode fragment, or explain why one algorithm scales better than another.

考试题目可能会要求你计算特定输入下的比较次数，识别给定伪代码片段的复杂度类别，或解释为什么某一种算法比另一种算法扩展性更好。

---

10. Tracing and Understanding Pseudocode | 追踪与理解伪代码

A common Edexcel question provides pseudocode for a searching or sorting algorithm and asks you to complete a trace table. Work through the loop line by line, updating each variable at every iteration, and pay special attention to loop conditions and off-by-one errors.

Edexcel 常见题型会给出搜索或排序算法的伪代码，并要求你完成追踪表。逐行执行循环，在每次迭代中更新每个变量，特别注意循环条件和边界错误。

You should be comfortable converting between a written description of an algorithm, pseudocode and actual code in your chosen language. Practise writing binary search both iteratively and recursively, and practise implementing bubble, insertion, merge and quick sort from scratch.

你应该能够熟练地在算法的文字描述、伪代码和你所选语言的实际代码之间进行转换。练习迭代和递归两种方式编写二分搜索，并练习从头实现冒泡、插入、归并和快速排序。

When writing pseudocode in the exam, use clear variable names, consistent indentation and simple logic. Marks are awarded for correct algorithm structure even if the syntax is not perfect, so do not waste time on language-specific details.

在考试中编写伪代码时，使用清晰的变量名、一致的缩进和简单的逻辑。即使语法不完美，只要算法结构正确就能得分，因此不要把时间浪费在语言特有的细节上。

---

11. Stability, In-place and Recursion | 稳定性、原地性与递归

A sorting algorithm is stable if equal elements keep their original relative order. Bubble sort, insertion sort and merge sort are stable; quick sort is usually unstable, depending on the partitioning strategy.

如果排序算法使相等元素保持原来的相对顺序，则称该算法是稳定的。冒泡排序、插入排序和归并排序是稳定的；快速排序通常不稳定，具体取决于分区策略。

An algorithm is in-place if it requires only a constant amount of extra memory beyond the input. Bubble sort, insertion sort and quick sort are in-place; merge sort requires O(n) additional space.

如果算法除了输入外只需要常量级额外内存，则称该算法是原地算法。冒泡排序、插入排序和快速排序是原地算法；归并排序需要 O(n) 额外空间。

Recursion is central to merge sort, quick sort and recursive binary search. Every recursive algorithm needs a base case to stop the recursion, and each recursive call should reduce the problem size toward that base case.

递归是归并排序、快速排序和递归二分搜索的核心。每个递归算法都需要一个基准情形来停止递归，并且每次递归调用都应使问题规模向该基准情形缩小。

---

12. Exam Technique and Common Pitfalls | 考试技巧与常见错误

Always check whether the data is sorted before recommending binary search. Many students lose marks by applying binary search to unsorted data or by forgetting to mention that sorting must happen first.

在推荐二分搜索之前，一定要检查数据是否已排序。许多学生因将二分搜索应用于未排序数据，或忘记提及必须先排序而丢分。

When comparing algorithms, mention time complexity, space complexity, stability and whether the algorithm works on sorted or unsorted data. A well-rounded justification is more likely to gain full marks than a single sentence about speed.

比较算法时，要提及时间复杂度、空间复杂度、稳定性以及算法是否适用于已排序或未排序的数据。全面的论证比只谈速度的一句话更能获得满分。

For sorting questions, identify whether the algorithm is stable and in-place. For searching questions, calculate the exact number of comparisons in a trace table, and be careful with integer division when finding the midpoint: mid = left + (right – left) // 2 avoids overflow in some languages.

对于排序题，要判断算法是否稳定、是否原地。对于搜索题，要在追踪表中计算确切的比较次数，并在求中点时注意整数除法：mid = left + (right – left) // 2 可以避免某些语言中的溢出问题。

Published by TutorHao | Programming Revision Series | aleveler.com

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