📚 Searching and Sorting Algorithms for Edexcel A-Level Computer Science | Edexcel A Level 编程：查找与排序算法
In Edexcel A-Level Computer Science, algorithms for searching and sorting form the backbone of many programming questions. You need to trace, compare and implement these algorithms under timed conditions. This revision guide covers linear search, binary search, bubble sort, insertion sort, merge sort and quick sort, with pseudocode and complexity analysis.
在 Edexcel A-Level 计算机科学中，查找与排序算法是许多编程题的核心。你需要在限时条件下跟踪、比较并实现这些算法。本复习指南涵盖线性查找、二分查找、冒泡排序、插入排序、归并排序和快速排序，并提供伪代码与复杂度分析。
1. The Role of Algorithms in Programming | 算法在编程中的作用
An algorithm is a step-by-step sequence of instructions that solves a problem. Searching and sorting are fundamental operations used by many larger programs. In the Edexcel specification, you must be able to trace algorithms, write pseudocode, and evaluate time and space complexity.
算法是逐步解决问题的指令序列。查找和排序是许多大型程序使用的基本操作。在 Edexcel 考试规范中，你需要能够跟踪算法、编写伪代码，并评估时间复杂度和空间复杂度。
- Searching: locating a target value in a data structure. | 查找：在数据结构中定位目标值。
- Sorting: arranging data into ascending or descending order. | 排序：将数据按升序或降序排列。
- Time complexity: how the number of steps grows with input size n. | 时间复杂度：步骤数随输入规模 n 的增长情况。
2. Linear Search | 线性查找
Linear search starts at the first element and checks each item in turn until the target is found or the list ends. It works on unsorted lists and is simple to implement, but becomes slow on large datasets.
线性查找从第一个元素开始，依次检查每个元素，直到找到目标值或到达列表末尾。它适用于未排序列表，实现简单，但在大型数据集上速度较慢。
for i = 0 to n-1
if list[i] == target then return i
return -1
Average and worst-case time complexity is O(n); best case is O(1) when the target is the first element.
平均和最坏时间复杂度为 O(n)；当目标值是第一个元素时，最好情况为 O(1)。
3. Binary Search | 二分查找
Binary search repeatedly divides a sorted list in half. It compares the middle element with the target, discarding the half that cannot contain the target. This makes it far faster than linear search on large sorted arrays.
二分查找不断将已排序列表分成两半。它将中间元素与目标值比较，丢弃不可能包含目标值的那一半。因此在大型已排序数组上，其速度远快于线性查找。
low = 0
high = n - 1
while low <= high
mid = (low + high) div 2
if list[mid] == target then return mid
else if list[mid] < target then low = mid + 1
else high = mid - 1
return -1
Binary search requires a sorted list. Its time complexity is O(log n) in the worst case, and O(1) in the best case when the middle element is the target.
二分查找要求列表已排序。其最坏时间复杂度为 O(log n)，最好情况为 O(1)，即中间元素就是目标值。
4. Comparing Search Efficiency: Big O Notation | 查找效率对比：大 O 表示法
Big O notation describes how the number of operations grows with input size n. O(n) means linear growth; O(log n) means logarithmic growth. For 1 million elements, linear search may take up to 1,000,000 comparisons, while binary search takes about 20.
大 O 表示法描述运算次数如何随输入规模 n 增长。O(n) 表示线性增长；O(log n) 表示对数增长。对于 100 万个元素，线性查找最多可能需要 1,000,000 次比较，而二分查找大约只需 20 次。
| Algorithm | Best | Average | Worst | Space |
|---|---|---|---|---|
| Linear Search | O(1) | O(n) | O(n) | O(1) |
| Binary Search | O(1) | O(log n) | O(log n) | O(1) |
Choosing the right search algorithm depends on whether the data is sorted and how often searches are performed. Binary search is preferred for large sorted datasets.
选择正确的查找算法取决于数据是否已排序以及查找频率。对于大型已排序数据集，二分查找更受青睐。
5. Bubble Sort | 冒泡排序
Bubble sort repeatedly steps through the list, compares adjacent items, and swaps them if they are in the wrong order. After each pass, the largest unsorted element bubbles to the end. It is stable and easy to code, but inefficient for large n.
冒泡排序反复遍历列表，比较相邻元素，如果顺序错误则交换。每完成一轮，未排序部分的最大元素就会“冒泡”到末尾。它稳定且易于编写，但对大规模数据效率低。
for i = 0 to n - 2
for j = 0 to n - 2 - i
if list[j] > list[j + 1] then swap(list[j], list[j + 1])
Bubble sort has O(n²) average and worst-case time complexity. With a flag to detect no swaps, the best case is O(n) when the list is already sorted.
冒泡排序的平均和最坏时间复杂度为 O(n²)。若使用标志检测无交换，则当列表已排序时最好情况为 O(n)。
6. Insertion Sort | 插入排序
Insertion sort builds a sorted portion one item at a time. It takes the next element and inserts it into its correct position among the items already sorted. It is efficient for small or nearly sorted lists and is stable.
插入排序一次一个元素地构建有序部分。它取出下一个元素并将其插入到已排序部分的正确位置。它对于小规模或近似有序的列表效率较高，并且是稳定的。
for i = 1 to n - 1
key = list[i]
j = i - 1
while j >= 0 and list[j] > key
list[j + 1] = list[j]
j = j - 1
list[j + 1] = key
Insertion sort has O(n²) average and worst-case time complexity. The best case is O(n) when the list is already nearly sorted.
插入排序的平均和最坏时间复杂度为 O(n²)。当列表已接近有序时，最好情况为 O(n)。
7. Merge Sort | 归并排序
Merge sort uses divide and conquer. It splits the list into two halves, recursively sorts each half, and then merges the two sorted halves into one sorted list. Its O(n log n) complexity makes it efficient for large lists, but it requires extra memory.
归并排序采用分治法。它将列表分成两半，递归地对每半进行排序，然后将两个有序半部分合并为一个有序列表。其 O(n log n) 复杂度使其适合大型列表，但需要额外内存。
function mergeSort(list)
if length(list) <= 1 then return list
mid = length(list) div 2
left = mergeSort(list[0 : mid])
right = mergeSort(list[mid : length])
return merge(left, right)
Merge sort has O(n log n) time complexity in all cases. Its space complexity is O(n) because the merge step requires a temporary array.
归并排序在所有情况下时间复杂度均为 O(n log n)。其空间复杂度为 O(n)，因为合并步骤需要一个临时数组。
8. Quick Sort | 快速排序
Quick sort also uses divide and conquer. It selects a pivot, partitions the list into elements smaller and larger than the pivot, and recursively sorts the partitions. Its average complexity is O(n log n), but a bad pivot choice can degrade to O(n²).
快速排序同样采用分治法。它选择一个基准值，将列表划分为小于基准和大于基准的两部分，然后递归排序各分区。其平均复杂度为 O(n log n)，但糟糕的基准选择会退化为 O(n²)。
function quickSort(list)
if length(list) <= 1 then return list
pivot = list[0]
less = all items < pivot
greater = all items > pivot
return quickSort(less) + [pivot] + quickSort(greater)
Quick sort is usually faster than merge sort in practice because of better cache performance, but it is not stable. Many implementations use the middle element as pivot to reduce the chance of worst-case behaviour.
快速排序在实践中通常比归并排序更快，因为缓存性能更好，但它不稳定。许多实现选择中间元素作为基准，以降低出现最坏情况的概率。
9. Comparing Sorting Algorithms | 排序算法比较
The table below summarises the key properties of the four sorting algorithms required by the Edexcel specification. Knowing this table by heart will help you answer both multiple-choice and extended questions.
下表总结了 Edexcel 规范要求的四种排序算法的关键属性。记住这张表有助于你解答选择题和扩展题。
| Algorithm | Best | Average | Worst | Space | Stable |
|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
For small or nearly sorted data, insertion sort often performs very well. For large or completely unsorted data, merge sort and quick sort are usually the best choices.
对于小型或近似有序的数据，插入排序通常表现很好。对于大型或完全无序的数据，归并排序和快速排序通常是最佳选择。
10. Algorithm Design and Pseudocode | 算法设计与伪代码
In Edexcel exams, you may be asked to write pseudocode for a simple search or sort, or to modify an algorithm. Use clear variable names, indentation, and the standard keywords IF, WHILE, FOR, RETURN. Avoid language-specific syntax.
在 Edexcel 考试中，你可能需要编写简单查找或排序的伪代码，或修改算法。使用清晰的变量名、缩进和标准关键字 IF、WHILE、FOR、RETURN。避免特定语言语法。
- Use DIV and MOD for integer division and remainder. | 使用 DIV 和 MOD 表示整数除法和取余。
- Use length(list) or n to denote list size. | 使用 length(list) 或 n 表示列表长度。
- Use indentation to show block structure. | 使用缩进显示块结构。
- Return -1 or a message when a search target is not found. | 当查找目标不存在时，返回 -1 或提示信息。
11. Common Mistakes and Exam Tips | 常见错误与考试技巧
Many marks are lost through small errors in tracing or pseudocode. Watch out for the following common pitfalls when revising searching and sorting algorithms.
许多失分源于跟踪或伪代码中的小错误。复习查找和排序算法时请注意以下常见陷阱。
- Forgetting that binary search requires a sorted list. | 忘记二分查找要求列表已排序。
- Confusing best, average and worst-case complexities. | 混淆最好、平均和最坏情况复杂度。
- Using wrong index ranges in bubble sort loops. | 冒泡排序循环中使用错误的索引范围。
- Ignoring stability when a question asks about preserving equal elements. | 当题目要求保留相等元素的相对顺序时忽略稳定性。
- Not checking edge cases such as an empty list or a single element. | 未检查空列表或单个元素等边界情况。
12. Further Practice | 拓展练习
Practice tracing the algorithms on small arrays of numbers. Try writing pseudocode from memory, then compare with the textbook. Use past Edexcel questions to test your ability to explain complexity and identify algorithm type from a trace.
练习在小数字数组上跟踪算法。尝试凭记忆编写伪代码，然后与教科书比较。使用历年 Edexcel 真题测试你解释复杂度和从跟踪中识别算法类型的能力。
For additional challenge, modify the algorithms to sort in descending order, or adapt binary search to return the position where a target should be inserted.
想增加挑战，可以修改算法使其按降序排序，或调整二分查找以返回目标值应插入的位置。
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图