A-Level Programming Algorithms: Searching, Sorting and Complexity | A-Level 编程算法：查找、排序与复杂度

📚 A-Level Programming Algorithms: Searching, Sorting and Complexity | A-Level 编程算法：查找、排序与复杂度

Searching and sorting algorithms are the cornerstones of Edexcel A-Level programming. This topic connects abstract logical thinking with real program performance, and exam questions require you to trace code, compare Big O efficiency and justify algorithm choices.

查找与排序算法是 Edexcel A-Level 编程的基石。这一主题将抽象逻辑思维与真实程序性能相结合，考试题目要求你跟踪代码、比较大 O 效率并证明算法选择的合理性。

1. What Is an Algorithm? | 什么是算法？

An algorithm is a finite sequence of well-defined steps that solves a specific problem. For Edexcel, you must be able to express algorithms in pseudocode, flowcharts and program code, and reason about their efficiency.

算法是解决特定问题的有限且定义明确的步骤序列。对于 Edexcel，你必须能够用伪代码、流程图和程序代码表达算法，并对其效率进行推理。

Key properties include clarity, termination, input and output. An algorithm must be precise enough for another programmer to implement it without ambiguity. For example, the instruction “sort the list” is not an algorithm because it does not state the exact comparison and swapping steps.

关键性质包括清晰性、终止性、输入和输出。算法必须足够精确，使另一位程序员能够无歧义地实现它。例如，”对列表进行排序”这一指令不是算法，因为它没有说明确切的比较和交换步骤。

• Input: values supplied to the algorithm | 输入：提供给算法的值
• Output: at least one result produced | 输出：至少产生一个结果
• Termination: stops after finite steps | 终止性：在有限步骤后停止
• Definiteness: every step is clear and unambiguous | 明确性：每一步都清晰且无歧义

2. Linear Search | 线性查找

Linear search scans a list from index 0 to n-1, comparing each element with the target. It works on any list, whether sorted or unsorted, so it is useful when you have no guarantee about ordering.

线性查找从索引 0 到 n-1 扫描列表，将每个元素与目标值进行比较。它对任何列表都有效，无论是有序还是无序，因此当你无法保证顺序时非常有用。

Suppose we search for 42 in the list [15, 9, 42, 6, 30]. Linear search compares 15, then 9, then finds 42 at index 2 after 3 comparisons. If the target were 99, it would examine all 5 elements and return not found.

假设我们在列表 [15, 9, 42, 6, 30] 中查找 42。线性查找依次比较 15、9，然后在索引 2 处找到 42，共比较 3 次。如果目标值是 99，它将检查全部 5 个元素并返回未找到。

Its worst-case time complexity is O(n) because every element may need checking. For a list of 1,000 items, a full scan averages 500 comparisons and may need 1,000 when the target is absent or is the final element.

其最坏时间复杂度是 O(n)，因为可能需要检查每个元素。对于包含 1,000 个元素的列表，完整扫描平均需要 500 次比较，当目标不存在或是最后一个元素时最多可能需要 1,000 次。

• Best case: O(1) when target is first | 最佳情况：目标在首位时为 O(1)
• Worst case: O(n) when target is last or absent | 最坏情况：目标在末位或不存在时为 O(n)
• Average case: O(n) for random input | 平均情况：随机输入为 O(n)

3. Binary Search | 二分查找

Binary search operates only on a sorted list. It finds the middle element, compares it

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

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