Searching, Sorting and Big O Complexity | 搜索、排序与大 O 复杂度

📚 Searching, Sorting and Big O Complexity | 搜索、排序与大 O 复杂度

In Edexcel A-Level Programming, algorithm efficiency is a central theme. Knowing how to search and sort data, and how to express performance with Big O notation, is essential for both written papers and practical programming tasks. This article covers the key searching and sorting algorithms, their time complexity, and how to choose between them.

在 Edexcel A-Level 编程中，算法效率是核心主题。了解如何搜索和排序数据，以及如何用大 O 表示法表达性能，对于笔试和实践编程任务都至关重要。本文涵盖关键的搜索和排序算法、它们的时间复杂度以及如何在它们之间做出选择。

1. Computational Thinking and Algorithm Design | 计算思维与算法设计

An algorithm is a finite sequence of well-defined instructions designed to solve a problem. Before writing code, programmers use computational thinking, which involves decomposition, pattern recognition, abstraction and algorithm design.

算法是为解决问题而设计的有穷、步骤明确的指令序列。在编写代码之前，程序员运用计算思维，包括分解、模式识别、抽象和算法设计。

In the Edexcel course, you are expected to trace algorithms by hand and identify the steps required to carry out a search or sort. This skill is tested through dry runs and code tracing questions.

在 Edexcel 课程中，你应能手写追踪算法并识别执行搜索或排序所需的步骤。这一技能通过干运行和代码追踪题来考查。

When you design an algorithm, you must consider both correctness and efficiency. A correct algorithm produces the right output for all valid inputs, while an efficient algorithm does so within acceptable time and memory limits.

设计算法时，必须同时考虑正确性和效率。正确的算法对所有有效输入产生正确输出，而高效的算法能在可接受的时间和内存限制内完成。

---

2. Linear Search | 线性搜索

Linear search checks each element of a list in order until the target is found or the list ends. It works on unsorted data, which makes it flexible, but it can be slow for large lists.

线性搜索按顺序检查列表中的每个元素，直到找到目标或列表结束。它适用于未排序的数据，因此非常灵活，但对大型列表可能较慢。

In the worst case, linear search has a time complexity of O(n), where n is the number of items, because every element may need to be examined before the target is found or the list ends.

在最坏情况下，线性搜索的时间复杂度为 O(n)，其中 n 是项数，因为在找到目标或列表结束之前可能需要检查每个元素。

Despite its simplicity, linear search is useful for small data sets or when the data cannot be sorted. It is also the only option when data is stored in an unordered linked list.

尽管简单，线性搜索在小型数据集或数据无法排序时仍然有用。当数据存储在无序链表中时，它也是唯一的选择。

---

3. Binary Search | 二分搜索

Binary search repeatedly divides a sorted list in half to locate a target. It compares the middle element with the target and discards the half that cannot contain the target.

二分搜索反复将已排序列表分成两半以定位目标。它比较中间元素与目标，并丢弃不可能包含目标的那一半。

Because the search space is halved at each step, binary search has a time complexity of O(log₂ n), making it much faster than linear search for large sorted lists.

由于每步将搜索空间减半，二分搜索的时间复杂度为 O(log₂ n)，对大型有序列表远快于线性搜索。

Binary search complexity: O(log₂ n)

A common exam pitfall is applying binary search to an unordered list, which is invalid and gives unpredictable results. Always check that the data is sorted before using binary search.

常见的考试误区是将二分搜索用于无序列表，这是无效的并且结果不可预测。使用二分搜索前务必确认数据已排序。

---

4. Bubble Sort | 冒泡排序

Bubble sort repeatedly steps through a list, compares adjacent items, and swaps them if they are in the wrong order. After each pass, the largest remaining element ‘bubbles’ to its final position.

冒泡排序反复遍历列表，比较相邻项，如果顺序错误则交换。每轮结束后，剩余最大元素“冒泡”到最终位置。

Bubble sort has worst-case and average time complexity O(n²), which makes it inefficient for large data sets, but it is easy to understand and implement.

冒泡排序最坏和平均时间复杂度为 O(n²)，使得它在大数据集上效率不高，但它易于理解和实现。

A useful optimisation is to stop early if a complete pass makes no swaps, because the list is already sorted. This gives a best-case time complexity of O(n) for an already sorted list.

一个有用的优化是：如果一整轮没有发生任何交换，则提前停止，因为列表已经有序。这使已排序列表的最佳时间复杂度为 O(n)。

---

5. Insertion Sort | 插入排序

Insertion sort builds a sorted portion of the list by taking one unsorted element at a time and inserting it into its correct position relative to the sorted part.

插入排序通过每次取出一个未排序元素并插入到已排序部分的正确位置，来逐步构建列表的已排序部分。

It is particularly efficient for small or nearly sorted data, with a best-case time complexity of O(n) and worst-case O(n²).

它特别适合小型或接近有序的数据，最佳时间复杂度为 O(n)，最坏为 O(n²)。

In exam questions, insertion sort is often traced with playing cards or a partially sorted array. You should be able to show the list after each insertion step.

在考试题中，插入排序常用扑克牌或部分有序数组进行追踪。你应该能够展示每次插入步骤后的列表状态。

---

6. Merge Sort | 归并排序

Merge sort uses a divide-and-conquer strategy: it recursively splits the list into halves until single elements remain, then merges the sorted halves back together.

归并排序使用分治策略：递归将列表分成两半，直到只剩单个元素，然后将有序的两半合并回来。

Merge sort has time complexity O(n log₂ n) in all cases, which makes it highly efficient for large lists, but it requires extra memory for merging.

归并排序在所有情况下时间复杂度为 O(n log₂ n)，对大型列表非常高效，但合并时需要额外内存。

Edexcel exams often ask you to show the merge process step by step, especially the merging of two sorted sublists into one sorted list.

Edexcel 考试常要求你逐步展示合并过程，尤其是两个有序子列表合并为一个有序列表的过程。

---

7. 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 time complexity is O(n log₂ n), but the worst case is O(n²), which occurs when the pivot is poorly chosen, such as always the smallest or largest element.

它的平均时间复杂度为 O(n log₂ n)，但最坏为 O(n²)，当基准选择不佳时，例如总是最小或最大元素时会出现。

There are different pivot selection methods: first, last, middle, or random. The method affects performance on certain data, and many implementations choose a median-of-three to reduce the chance of worst-case behaviour.

基准选择方式有多种：第一个、最后一个、中间或随机。方法会影响在特定数据上的性能，许多实现选择三数取中法来降低最坏情况出现的概率。

---

8. Big O Notation | 大 O 表示法

Big O notation describes how the running time or memory usage of an algorithm grows as the input size grows, ignoring constant factors and lower-order terms.

大 O 表示法描述算法运行时间或内存使用随输入规模增长的趋势，忽略常数因子和低阶项。

Common complexity classes include O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ) and O(n!).

常见复杂度类别包括 O(1)、O(log n)、O(n)、O(n log n)、O(n²)、O(2ⁿ) 和 O(n!)。

Complexity	Example algorithm	中文示例
O(1)	Array index access	数组索引访问
O(log n)	Binary search	二分搜索
O(n)	Linear search	线性搜索
O(n log n)	Merge sort, quick sort	归并排序、快速排序
O(n²)	Bubble sort, insertion sort	冒泡排序、插入排序

The key idea is asymptotic behaviour: how the algorithm scales when n becomes very large. Constant factors and lower-order terms are irrelevant for this measure.

核心思想是渐近行为：当 n 变得非常大时，算法如何扩展。常数因子和低阶项对这一度量无关紧要。

---

9. Comparing Algorithm Efficiency | 算法效率比较

When comparing algorithms, consider not only time complexity but also space complexity, whether data must be sorted, and stability of sorting.

比较算法时，不仅要考虑时间复杂度，还要考虑空间复杂度、数据是否必须有序以及排序稳定性。

Stable sorting preserves the relative order of equal elements. Merge sort and insertion sort are stable, while quick sort and bubble sort can be stable or unstable depending on implementation.

稳定排序保持相等元素的相对顺序。归并排序和插入排序是稳定的，而快速排序和冒泡排序取决于实现可以稳定或不稳定。

For searching, linear search requires no sorting but can be slow. Binary search is very fast but requires a sorted list. This trade-off is a common discussion point in exam answers.

对于搜索，线性搜索不需要排序但可能较慢。二分搜索非常快但需要有序列表。这种权衡是考试答案中常见的讨论点。

---

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

In practical programming tasks, choose an algorithm based on data size, whether the data is sorted, memory constraints, and how often the operation is performed.

在实际编程任务中，根据数据大小、数据是否有序、内存限制以及操作执行的频率来选择算法。

For small n, simpler algorithms such as linear search and insertion sort may be appropriate. For large n, binary search and merge sort are preferred because of their better scaling.

对于较小的 n，线性搜索和插入排序等简单算法可能更合适。对于较大的 n，优先选择二分搜索和归并排序，因为它们扩展性更好。

Edexcel questions may ask you to justify a choice or to compare algorithms using Big O notation. Always refer to the worst-case and average-case complexity when answering.

Edexcel 试题可能要求你用大 O 表示法证明选择或比较算法。回答时务必引用最坏情况和平均情况复杂度。

Understanding these fundamental algorithms gives you a strong foundation for solving programming problems, tracing code and scoring well on the A-Level examination.

理解这些基础算法能为你解决编程问题、追踪代码以及在 A-Level 考试中取得好成绩打下坚实基础。

Published by TutorHao | Computer Science Revision Series | aleveler.com

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