Searching and Sorting Algorithms | 搜索与排序算法

📚 Searching and Sorting Algorithms | 搜索与排序算法

Searching and sorting algorithms are core topics in Edexcel A-Level Computer Science. Understanding them helps you trace code, compare performance, and choose the right approach for a given scenario.

搜索与排序算法是 Edexcel A-Level 计算机科学的核心主题。理解它们有助于你跟踪代码、比较性能，并针对给定情景选择合适方法。

1. Why Algorithms Matter | 为什么算法很重要

Algorithms are precise step-by-step procedures. A small change in algorithm design can reduce execution time from hours to seconds on large data sets.

算法是精确的分步过程。算法设计上的微小改变，就能把大数据集上的执行时间从数小时缩短到数秒。

In Edexcel exams you will be asked to complete trace tables, identify the next step, or explain why one algorithm is more efficient than another.

在 Edexcel 考试中，你会被要求填写跟踪表、指出下一步，或解释为什么一种算法比另一种更高效。

Linear search and binary search — 线性搜索和二分搜索
Bubble sort, insertion sort, merge sort, quick sort — 冒泡排序、插入排序、归并排序、快速排序
Big-O notation — 大 O 表示法

2. Linear Search | 线性搜索

Linear search checks every element in a list from the first to the last until it finds the target value or reaches the end.

线性搜索从列表的第一个元素到最后一个元素逐一检查，直到找到目标值或到达列表末尾。

The algorithm can be described as follows:

该算法可以描述如下：

Start at index 0 — 从索引 0 开始
Compare the current element with the target — 将当前元素与目标值比较
If they match, return the index — 如果匹配，返回该索引
If not, increment the index and repeat — 如果不匹配，索引加一再重复
If the end is reached without a match, return ‘not found’ — 如果到达末尾仍未找到，返回“未找到”

Linear search works on unsorted data, which makes it very flexible. However, its worst-case and average-case time complexity is O(n), where n is the number of elements.

线性搜索可以处理未排序数据，因此非常灵活。然而，它的最坏和平均时间复杂度为 O(n)，其中 n 是元素个数。

Time complexity: O(n) in the worst case

最坏时间复杂度：O(n)

3. Binary Search | 二分搜索

Binary search is much faster than linear search, but it only works on a sorted list. It repeatedly divides the search space in half.

二分搜索比线性搜索快得多，但它只适用于已排序的列表。它反复将搜索范围缩小一半。

The key steps are:

关键步骤如下：

Set low to 0 and high to the last index — 设 low 为 0，high 为最后一个索引
Calculate the middle index using integer division — 使用整数除法计算中间索引
If the middle element equals the target, stop and return the index — 如果中间元素等于目标值，停止并返回索引
If the target is smaller, narrow to the left half — 如果目标更小，缩小到左半部分
If the target is larger, narrow to the right half — 如果目标更大，缩小到右半部分

mid = (low + high) DIV 2

中间索引 = (low + high) DIV 2

Each comparison halves the remaining search area. Therefore the number of steps grows logarithmically rather than linearly.

每次比较都会将剩余搜索区域减半。因此，步骤数以对数方式增长，而不是线性增长。

Time complexity: O(log₂ n)

时间复杂度：O(log₂ n)

For example, searching 1,000,000 sorted items takes at most about 20 comparisons using binary search, but up to 1,000,000 comparisons using linear search.

例如，在 1,000,000 个已排序项目中查找时，二分搜索最多约需要 20 次比较，而线性搜索最多可能需要 1,000,000 次比较。

4. Bubble Sort | 冒泡排序

Bubble sort repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. Each pass pushes the largest remaining element to its final position.

冒泡排序反复遍历列表，比较相邻元素，如果顺序错误就交换。每趟遍历将剩余的最大元素推到最终位置。

The algorithm uses two nested loops. The outer loop controls the number of passes, and the inner loop performs the comparisons and swaps.

该算法使用两层嵌套循环。外层循环控制遍历次数，内层循环执行比较和交换。

First pass moves the largest value to the end — 第一趟将最大值移到末尾
Second pass moves the second largest value to the second last position — 第二趟将第二大值移到倒数第二位置
Continue until no swaps are needed — 持续进行，直到不再需要交换

Bubble sort is simple to implement but inefficient for large lists. Its worst-case and average-case time complexity is O(n²).

冒泡排序实现简单，但对大型列表效率较低。其最坏和平均时间复杂度为 O(n²)。

Average and worst time complexity: O(n²)

平均和最坏时间复杂度：O(n²)

If the list is already sorted and the algorithm uses a swap flag, the best-case time complexity improves to O(n).

如果列表已经有序且算法使用了交换标记，最佳时间复杂度可提高到 O(n)。

5. Insertion Sort | 插入排序

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

插入排序在列表起始处构建有序部分。它取出每个新元素，并将其插入到有序部分中的正确位置。

This is similar to how a player sorts playing cards in their hand. The algorithm shifts larger elements to the right to make space for the inserted element.

这类似于玩家整理手中的扑克牌。算法将较大的元素向右移动，为待插入元素腾出空间。

Start from the second element — 从第二个元素开始
Compare it with elements in the sorted portion — 与有序部分中的元素比较
Shift larger elements right — 将较大的元素右移
Insert the current element in the gap — 将当前元素插入空位

Insertion sort is efficient for small or nearly sorted lists. Its average and worst-case time complexity is O(n²), but its best case is O(n).

插入排序适用于小型或接近有序的列表。其平均和最坏时间复杂度为 O(n²)，但最佳情况为 O(n)。

Best case: O(n) | Average and worst case: O(n²)

最佳情况：O(n) | 平均和最坏情况：O(n²)

6. Merge Sort | 归并排序

Merge sort uses a divide-and-conquer strategy. It recursively splits the list into halves until each sublist contains one element, then merges the sublists back together in sorted order.

归并排序采用分治策略。它递归地将列表拆分成两半，直到每个子列表只含一个元素，再按排序顺序将子列表合并回来。

Because a single-element list is already sorted, merging two sorted sublists is straightforward: compare the fronts and take the smaller element each time.

由于单元素列表已经有序，合并两个有序子列表很简单：每次比较两个子列表的前端，取较小的元素。

Divide: split the list into two halves — 分解：将列表分成两半
Recursively sort each half — 递归地对每一半排序
Merge the sorted halves — 合并已排序的两半

Merge sort guarantees O(n log n) time in the best, average, and worst cases. However, it requires O(n) extra space for the merging process.

归并排序在最佳、平均和最坏情况下都保证 O(n log n) 时间。然而，它在合并过程中需要 O(n) 的额外空间。

Time complexity: O(n log n) in all cases

时间复杂度：所有情况下均为 O(n log n)

Merge sort is stable, which means equal elements keep their original relative order. This is useful when sorting by multiple keys.

归并排序是稳定的，这意味着相等元素保持原有相对顺序。这在按多个键排序时非常有用。

7. Quick Sort | 快速排序

Quick sort also uses divide and conquer, but it works by selecting a pivot element and partitioning the list around it.

快速排序也使用分治法，但它通过选择一个基准元素并围绕该元素对列表进行分区。

Choose a pivot — 选择一个基准
Place elements smaller than the pivot on the left — 将小于基准的元素放在左边
Place elements larger than the pivot on the right — 将大于基准的元素放在右边
Recursively sort the left and right partitions — 递归地对左右分区排序

If the pivot divides the list evenly, quick sort runs in O(n log n). If the pivot is consistently the smallest or largest element, the time degrades to O(n²).

如果基准能均匀划分列表，快速排序的运行时间为 O(n log n)。如果基准总是最小或最大元素，时间会退化到 O(n²)。

Average case: O(n log n) | Worst case: O(n²)

平均情况：O(n log n) | 最坏情况：O(n²)

In practice, quick sort is often faster than merge sort because it sorts in place and uses less extra memory, typically O(log n) for the recursion stack.

实际上，快速排序通常比归并排序更快，因为它是原地排序，额外内存较少，通常仅需 O(log n) 的递归栈空间。

8. Comparing Time Complexities | 时间复杂度对比

The table below summarises the key algorithms you need to know for Edexcel A-Level Programming.

下表总结了你需要掌握的 Edexcel A-Level 编程关键算法。

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)
Bubble Sort	O(n)	O(n²)	O(n²)	O(1)
Insertion Sort	O(n)	O(n²)	O(n²)	O(1)
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)
Quick Sort	O(n log n)	O(n log n)	O(n²)	O(log n)

9. Choosing the Right Algorithm | 选择合适的算法

When selecting a searching algorithm, first check whether the data is sorted. If it is sorted, binary search is almost always the better choice.

选择搜索算法时，首先检查数据是否已排序。如果已排序，二分搜索几乎总是更好的选择。

If the data is unsorted and cannot be sorted cheaply, linear search remains the practical option.

如果数据未排序且排序成本较高，线性搜索仍是实际选择。

For sorting, the choice depends on data size, memory limits, and whether stability matters.

对于排序，选择取决于数据规模、内存限制以及是否需要稳定性。

Small or nearly sorted data: insertion sort — 小型或接近有序的数据：插入排序
Large data with guaranteed time: merge sort — 大型数据且需要保证时间：归并排序
Large data with memory constraints: quick sort — 大型数据但内存有限：快速排序
Simple teaching example: bubble sort — 简单教学示例：冒泡排序

10. Exam Technique and Common Pitfalls | 考试技巧与常见误区

In Edexcel exams, trace tables are often worth several marks. Show the values of all variables after each pass or iteration.

在 Edexcel 考试中，跟踪表通常占好几分。要展示每次遍历或迭代后所有变量的值。

A common mistake is forgetting that binary search only works on sorted data. If the question does not state the list is sorted, you cannot assume binary search is valid.

一个常见错误是忘记二分搜索只适用于已排序数据。如果题目没有说明列表已排序，就不能假定二分搜索有效。

Another pitfall is confusing O(n) with O(log n). Remember that binary search halves the search space, so its time grows much more slowly than linear search.

另一个误区是混淆 O(n) 与 O(log n)。请记住，二分搜索将搜索空间减半，因此其时间增长远慢于线性搜索。

Always check the precondition of each algorithm — 始终检查每个算法的前置条件
Count comparisons and swaps carefully when completing trace tables — 填写跟踪表时仔细计算比较和交换次数
Use Big-O notation to justify algorithm choice in written answers — 在书面答案中使用大 O 表示法来论证算法选择

11. Summary | 总结

Searching and sorting algorithms are central to A-Level Programming. You should be able to trace them, compare their time and space complexity, and choose the best algorithm for a given scenario.

搜索与排序算法是 A-Level 编程的核心。你应该能够跟踪它们、比较它们的时间和空间复杂度，并为给定情景选择最佳算法。

Linear search is simple but slow; binary search is fast but requires sorted data. Bubble and insertion sorts are simple O(n²) algorithms, while merge sort and quick sort are efficient O(n log n) algorithms

Published by TutorHao | A-Level 编程 Revision Series | aleveler.com

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

Searching and Sorting Algorithms | 搜索与排序算法