📚 Mastering Searching and Sorting Algorithms | 掌握搜索与排序算法
Searching and sorting are fundamental programming techniques tested in the Edexcel A-Level Computer Science specification. Understanding how each algorithm works, its complexity, and when to use it is essential for both the practical programming unit and the written exam.
搜索和排序是爱德思 A-Level 计算机科学大纲中的基础编程技术。了解每种算法的工作原理、复杂度以及何时使用，对实践编程单元和笔试都至关重要。
1. Linear Search | 线性搜索
Linear search examines each list element from the first to the last, comparing it with the target value. If a match is found, the index is returned; if the loop finishes without a match, the algorithm returns -1 or a ‘not found’ marker.
线性搜索从第一个元素到最后一个元素依次检查每个列表元素，并与目标值比较。如果找到匹配项，则返回索引；如果循环结束后没有找到匹配项，则返回 -1 或“未找到”标记。
It works on unsorted lists because it does not rely on any ordering property. It is easy to code, but for a list of n elements it may require up to n comparisons in the worst case.
它适用于未排序的列表，因为它不依赖任何顺序特性。编码简单，但对于包含 n 个元素的列表，最坏情况可能需要最多 n 次比较。
2. Binary Search | 二分搜索
Binary search is a divide-and-conquer technique that requires the list to be sorted in ascending or descending order. It compares the target with the middle element and eliminates half of the search space each time.
二分搜索是一种分治技术，要求列表按升序或降序排序。它比较目标值与中间元素，每次排除一半搜索空间。
mid = (low + high) ÷ 2
If the target equals the middle value, the search ends. If the target is smaller, the search continues in the left half; if larger, in the right half. The process repeats while low ≤ high.
如果目标值等于中间值，搜索结束。如果目标值较小，则在左半区继续搜索；如果较大，则在右半区继续搜索。当 low ≤ high 时重复此过程。
3. Comparing Search Algorithms | 比较搜索算法
Linear search is the only option when the data cannot be sorted, but binary search is significantly faster for large n. The trade-off is the need to maintain sorted order or pay sorting cost first.
当数据无法排序时，线性搜索是唯一选择；但对于大规模 n，二分搜索明显更快。代价是需要维护有序性，或先付出排序成本。
| Algorithm | Data requirement | Worst-case time | Space |
|---|---|---|---|
| Linear search | Unsorted or sorted | O(n) | O(1) |
| Binary search | Sorted | O(log n) | O(1) |
In exam questions, you must state that binary search requires sorted data and that its O(log n) behaviour comes from repeatedly halving the problem.
在考试题目中，你必须说明二分搜索需要有序数据，并且其 O(log n) 的行为来自问题的反复减半。
4. Bubble Sort | 冒泡排序
Bubble sort works by comparing adjacent pairs and swapping them if they are out of order. After each full pass, the next largest element is placed in its final position at the end of the list.
冒泡排序通过比较相邻元素对并在顺序错误时交换它们来工作。每完成一次完整遍历，下一个最大元素就会被放到列表末尾的最终位置。
The algorithm stops when a complete pass makes no swaps, meaning the list is sorted. Worst-case and average-case time complexity are both O(n²).
当一趟完整遍历没有发生任何交换时，算法停止，这意味着列表已经有序。最坏情况和平均情况的时间复杂度都是 O(n²)。
(n − 1) + (n − 2) + … + 1 = n(n − 1) ÷ 2
This formula shows the number of comparisons in the worst case when every adjacent pair has to be compared on every pass.
该公式显示了最坏情况下的比较次数，即每一趟都必须比较每一对相邻元素。
5. Insertion Sort | 插入排序
Insertion sort processes elements one by one, keeping the left side sorted. Each new element is compared with sorted elements from right to left, and larger elements are shifted right until the correct gap is found.
插入排序逐个处理元素，保持左侧有序。每个新元素从右到左与已排序元素比较，较大的元素右移，直到找到正确位置。
It is stable, uses O(1) extra space, and runs in O(n) time on an already sorted list. In the worst case, such as a reverse-sorted list, it degrades to O(n²).
它是稳定的，使用 O(1) 额外空间，在已经有序的列表上运行时间为 O(n)。最坏情况（如逆序列表）会退化到 O(n²)。
6. Merge Sort | 归并排序
Merge sort is a recursive divide-and-conquer algorithm. It repeatedly splits the list into halves, sorts each half, and then merges the two sorted halves by comparing the front elements.
归并排序是一种递归的分治算法。它反复将列表拆分为两半，分别排序，然后通过比较前部元素合并两个有序半区。
Merge sort has O(n log n) time complexity in all cases and is stable, but it requires O(n) auxiliary space for the merging process.
归并排序在所有情况下时间复杂度均为 O(n log n)，而且是稳定的，但合并过程需要 O(n) 的辅助空间。
T(n) = 2T(n ÷ 2) + O(n)
7. Quick Sort | 快速排序
Quick sort chooses a pivot and partitions the list into two parts: values less than the pivot and values greater than the pivot. The pivot is then in its final position, and the two partitions are sorted recursively.
快速排序选择一个基准值，将列表划分为两部分：小于基准值的元素和大于基准值的元素。基准值此时处于最终位置，然后递归地对两个分区进行排序。
The average time complexity is O(n log n), but poor pivot choices on already sorted data can cause O(n²) worst-case performance. It usually sorts in place using O(log n) stack space.
平均时间复杂度为 O(n log n)，但在已经有序的数据上选择较差的基准值可能导致 O(n²) 的最坏性能。它通常在原地排序，使用 O(log n) 栈空间。
8. Algorithm Efficiency and Big O | 算法效率与大 O 表示法
Big O notation gives an upper bound on the growth rate of an algorithm’s resource usage. Constants and lower-order terms are ignored because they matter less as n becomes large.
大 O 表示法给出了算法资源使用增长速率的上界。常数和低阶项被忽略，因为当 n 很大时它们的影响较小。
| Class | Example | Growth behaviour |
|---|---|---|
| O(1) | Indexing an array | Constant |
| O(log n) | Binary search | Halving each step |
| O(n) | Linear search | Linear |
| O(n log n) | Merge sort, quick sort average | Linearithmic |
| O(n²) | Bubble sort, insertion sort worst case | Quadratic |
In exam answers, always identify the dominant operation, such as comparisons or swaps, and explain how many times it executes as n grows.
考试作答时，务必识别主导操作，例如比较或交换，并解释它随着 n 增长执行了多少次。
9. Choosing the Right Algorithm | 选择合适的算法
For small lists, simple algorithms such as linear search, bubble sort, and insertion sort are acceptable because their coding simplicity reduces mistakes. For large data, binary search after sorting or merge sort is often preferable.
对于小列表，简单的算法如线性搜索、冒泡排序和插入排序是可接受的，因为它们编码简单、出错少。对于大规模数据，排序后二分搜索或归并排序通常更可取。
If stability matters, use insertion sort or merge sort; if average speed and low memory matter, quick sort is a strong candidate. Binary search is only valid on sorted data.
如果需要稳定性，使用插入排序或归并排序；如果平均速度和低内存更重要，快速排序是很强的候选。二分搜索只对有序数据有效。
10. Exam-Style Tips | 考试技巧
A-Level questions often ask you to trace an algorithm on a short list. Use a table with columns for index, values, comparisons, swaps, and pass number. Show every change clearly.
A-Level 题目常要求对短列表追踪算法。使用包含索引、值、比较、交换和趟数列的表格。清楚地显示每一次变化。
When explaining complexity, link the reasoning to the algorithm structure: binary search halves the search space, merge sort halves the problem and merges in linear time, bubble and insertion sorts use nested loops.
解释复杂度时，将推理与算法结构联系起来：二分搜索将搜索空间减半；归并排序将问题减半并以线性时间合并；冒泡排序和插入排序使用嵌套循环。
- State whether the data must be sorted
- Identify best, worst, and average cases
- Use Big O notation with n as the input size
- Justify comparisons and swaps in your trace
These habits will help you earn full marks for algorithm explanation and evaluation questions.
这些习惯将帮助你在算法解释和评估题中获得满分。
Published by TutorHao | Programming Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导