Sorting Algorithms in A-Level Computer Science | A-Level 计算机科学中的排序算法

📚 Sorting Algorithms in A-Level Computer Science | A-Level 计算机科学中的排序算法

Sorting algorithms are fundamental to computer science and appear regularly in the Edexcel A-Level programming syllabus. Understanding how they work, their efficiency, and when to apply each one is essential for both exams and real-world problem solving. This article explores the most common sorting algorithms, analyses their time and space complexity using Big O notation, and offers practical revision tips.

排序算法是计算机科学的基础，在 Edexcel A-Level 编程大纲中频繁出现。理解它们的工作原理、效率以及何时使用哪种算法，对于考试和现实问题解决都至关重要。本文将探讨最常见的排序算法，使用大 O 表示法分析其时间和空间复杂度，并提供实用的复习建议。

1. What are Sorting Algorithms? | 什么是排序算法？

A sorting algorithm is a step-by-step procedure used to rearrange elements in a list or array into a defined order, typically numerical or lexicographical. Sorting is a common operation in many programs, from displaying search results to preparing data for binary search. The choice of algorithm can dramatically affect performance, especially as the data set grows.

排序算法是一种逐步执行的流程，用于将列表或数组中的元素重新排列为定义的顺序，通常是数字或字典顺序。排序是许多程序中的常见操作，从显示搜索结果到为二分查找准备数据。算法的选择会显著影响性能，尤其是当数据集增大时。

There are two broad categories: comparison-based sorts, which compare elements to decide their order, and non-comparison sorts like radix sort. At A-Level, the focus is on comparison sorts: bubble sort, insertion sort, merge sort, and quick sort.

排序算法主要分为两大类：基于比较的排序（通过比较元素来决定顺序）和非比较排序（如基数排序）。在 A-Level 阶段，重点是基于比较的排序：冒泡排序、插入排序、归并排序和快速排序。

2. Bubble Sort | 冒泡排序

Bubble sort repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process is repeated until the list is sorted. The largest unsorted element ‘bubbles’ to its correct position at the end of the list with each full pass. It is simple to understand and implement but inefficient for large data sets.

冒泡排序反复遍历列表，比较相邻元素，如果顺序错误就交换它们。重复此过程直到列表有序。每次完整遍历都会使未排序部分的最大元素“冒泡”到列表末尾的正确位置。它简单易懂，实现方便，但对于大数据集效率很低。

Algorithm outline:

算法概要：

Start from the first element and compare it with the next one.
从第一个元素开始，与下一个元素比较。
If the current element is greater than the next, swap them.
如果当前元素大于下一个元素，则交换它们。
Move to the next position and repeat comparisons until the end of the list is reached.
移动到下一位置并重复比较，直到列表末尾。
After one full pass, the largest element is at the end. Repeat the entire process for the remaining unsorted portion (i.e., excluding the last sorted element each time).
一次完整遍历后，最大元素已在末尾。对剩余未排序部分（即每次排除最后一个已排序元素）重复整个过程。
Continue until no swaps are needed in a pass.
继续直到某次遍历中无需交换为止。

Time complexity: worst-case and average-case O(n²), best-case O(n) when the list is already sorted and an optimisation flag is used. Space complexity: O(1), as it sorts in-place.

时间复杂度：最坏和平均情况为 O(n²)，最好情况（当列表已经有序且使用了优化标记时）为 O(n)。空间复杂度为 O(1)，因为它原地排序。

3. Insertion Sort | 插入排序

Insertion sort builds the final sorted list one element at a time. It takes each element from the unsorted part and inserts it into its correct position within the sorted part. It is efficient for small data sets and works well with data that is already partially sorted.

插入排序每次取一个元素构建最终有序列表。它从无序部分取出每个元素，并将其插入到有序部分的正确位置。它适用于小数据集，并且在数据已经部分有序时表现良好。

How it works:

工作方式：

Assume the first element is a sorted sublist of size 1.
假设第一个元素是大小为1的有序子列表。
Take the next element and compare it with elements in the sorted sublist from right to left.
取下一个元素，从右向左与有序子列表中的元素比较。
Shift all larger elements one position to the right to make space, and insert the new element into the correct slot.
将所有较大的元素向右移动一位以腾出空间，然后将新元素插入正确的槽位。
Repeat for all remaining elements in the unsorted part.
对无序部分中的所有剩余元素重复此操作。

Time complexity: O(n²) in worst and average cases, O(n) in best case (already sorted). Space complexity: O(1) in-place. Insertion sort is stable, meaning it preserves the relative order of equal elements.

时间复杂度：最坏和平均情况 O(n²)，最佳情况 O(n)（已排序）。空间复杂度：O(1) 原地排序。插入排序是稳定的，即保持相等元素的相对顺序。

4. Merge Sort | 归并排序

Merge sort is a divide-and-conquer algorithm that splits the list into smaller sublists, recursively sorts them, and then merges the sorted sublists back together. It guarantees O(n log n) time complexity in all cases, making it highly efficient for large data sets. However, it requires additional memory for the merging process.

归并排序是一种分治算法，它将列表分割成较小的子列表，递归排序它们，然后将有序子列表合并在一起。它在所有情况下都能保证 O(n log n) 的时间复杂度，因此对大数据集非常高效。但合并过程需要额外的内存。

Steps:

步骤：

Divide the unsorted list into two halves recursively until each sublist contains only one element (a single element is trivially sorted).
将未排序列表递归地分成两半，直到每个子列表只包含一个元素（单个元素显然是有序的）。
Repeatedly merge sublists to produce new sorted sublists. Take two adjacent sublists, compare their front elements, and place the smaller one into the merged list. Continue until all elements from both sublists are processed.
反复合并子列表以生成新的有序子列表。取两个相邻子列表，比较它们的前端元素，将较小的一个放入合并列表。继续直到两个子列表的所有元素都被处理。
Continue merging until there is only one sorted list remaining.
持续合并直到只剩下一个有序列表。

Time complexity: O(n log n) in worst, average, and best cases. Space complexity: O(n) auxiliary space for the temporary arrays during merging. Merge sort is stable and works well for linked lists due to its sequential access pattern.

时间复杂度：最坏、平均和最佳情况均为 O(n log n)。空间复杂度：合并过程中需要 O(n) 的辅助空间。归并排序是稳定的，并且由于其顺序访问模式，非常适合链表。

5. Quick Sort | 快速排序

Quick sort is another divide-and-conquer algorithm. It selects a ‘pivot’ element and partitions the list so that all elements smaller than the pivot come before it, and all greater elements come after. The sublists are then recursively sorted. Its average performance is excellent, but the worst-case scenario occurs with poor pivot choices.

快速排序是另一种分治算法。它选择一个“枢轴”元素，并划分列表，使得所有小于枢轴的元素在其前面，所有大于枢轴的元素在其后面。然后递归排序子列表。它的平均性能极佳，但如果枢轴选择不佳，会出现最坏情况。

Process:

过程：

Choose a pivot element (common strategies: first element, last element, random, or median-of-three).
选择一个枢轴元素（常用策略：首元素、尾元素、随机或三数取中）。
Partition the list: move all elements less than the pivot to the left and all greater elements to the right. The pivot ends up in its final sorted position.
划分列表：将所有小于枢轴的元素移至左侧，大于的元素移至右侧。枢轴最终处于其最终排序位置。
Recursively apply quick sort to the left and right sublists.
递归地对左右子列表应用快速排序。

Time complexity: average O(n log n), worst-case O(n²) when the smallest or largest element is consistently chosen as pivot. Space complexity: O(log n) on average for the recursion stack; O(n) in worst case. Quick sort is generally not stable but can be implemented in-place.

时间复杂度：平均 O(n log n)，当总是选择最小或最大元素作为枢轴时，最坏情况为 O(n²)。空间复杂度：平均 O(log n)（递归栈），最坏 O(n)。快速排序通常不稳定，但可以原地实现。

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

Choosing the right sorting algorithm depends on the size of the data, the degree of pre-sortedness, memory constraints, and stability requirements. For small or nearly sorted data sets, insertion sort can outperform merge sort and quick sort due to lower constant factors. Bubble sort is rarely used in practice except for educational purposes.

选择正确的排序算法取决于数据大小、预先有序的程度、内存限制以及稳定性要求。对于小数据集或接近有序的数据集，插入排序可能因常数因子较低而优于归并排序和快速排序。冒泡排序除了教学目的外，在实践中很少使用。

Here is a summary table comparing the four algorithms:

以下是四种算法的比较汇总表：

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

7. Big O Notation and Complexity Classes | 大 O 表示法与复杂度等级

Big O notation describes the upper bound of an algorithm’s running time or space usage as the input size grows. It focuses on the dominant term and ignores constant factors. At Edexcel A-Level, you must be able to evaluate and compare algorithms using Big O.

大 O 表示法描述了随着输入规模增长，算法运行时间或空间占用的上界。它关注主导项，忽略常数因子。在 Edexcel A-Level 中，你必须能够使用大 O 评估和比较算法。

Common complexities in sorting:

排序中常见的复杂度：

O(1): constant time (e.g., swap two elements).
O(1)：常数时间（例如交换两个元素）。
O(log n): logarithmic time (e.g., binary search; in sorting, it often appears in the depth of recursive calls).
O(log n)：对数时间（如二分查找；在排序中常体现在递归调用的深度）。
O(n): linear time (e.g., one pass through the data; best-case for insertion sort).
O(n)：线性时间（如遍历数据一遍；插入排序的最佳情况）。
O(n log n): linearithmic time (merge sort, average quick sort; often the best achievable for comparison-based sorting).
O(n log n)：线性对数时间（归并排序、快速排序平均情况；通常是基于比较排序的最佳可实现复杂度）。
O(n²): quadratic time (bubble sort, insertion sort average/worst).
O(n²)：二次时间（冒泡排序、插入排序的平均/最坏情况）。

To determine complexity, count the number of fundamental operations as a function of n. For example, bubble sort performs about n²/2 comparisons in the worst case, giving O(n²).

确定复杂度时，将基本操作次数表示为 n 的函数。例如，冒泡排序在最坏情况下大约执行 n²/2 次比较，因此为 O(n²)。

8. Space Complexity and In-Place Sorting | 空间复杂度与原地排序

Space complexity measures the extra memory an algorithm needs beyond the input data. An in-place sorting algorithm uses only a constant amount of auxiliary space (O(1)). Bubble sort and insertion sort are in-place. Merge sort requires O(n) additional space for merging, while quick sort uses O(log n) stack space on average, making it in-place under some definitions but not strictly if we count the recursion stack.

空间复杂度衡量算法在输入数据之外所需的额外内存。原地排序算法仅使用常量辅助空间（O(1)）。冒泡排序和插入排序是原地排序。归并排序需要 O(n) 的额外空间用于合并，而快速排序平均使用 O(log n) 的栈空间，在某些定义下算是原地，但如果计递归栈则不是严格原地。

At A-level, you need to identify the auxiliary space used by each algorithm and discuss its trade-offs. In scenarios with limited memory, in-place sorts are preferred.

在 A-Level 中，你需要识别每种算法使用的辅助空间，并讨论其取舍。在内存有限的场景下，应优先选择原地排序。

9. Stable vs Unstable Sorting | 稳定排序与不稳定排序

A sorting algorithm is stable if it preserves the relative order of equal elements. For example, when sorting a list of students by grade, a stable sort will keep students with the same grade in their original order. Stability matters when sorting by multiple keys (e.g., sort by surname then by grade). Merge sort and insertion sort are stable; quick sort and bubble sort can be stable or unstable depending on implementation, though typical quick sort is unstable.

如果排序算法保持相等元素的相对顺序，则称其为稳定的。例如，按成绩对学生列表排序时，稳定排序会让成绩相同的学生保持原始顺序。在按多个关键字排序时（如先按姓氏再按成绩），稳定性很重要。归并排序和插入排序是稳定的；快速排序和冒泡排序的稳定性取决于实现，但典型的快速排序是不稳定的。

In exam questions, you may be asked to explain the concept or analyse whether a given trace shows stable behaviour.

在考题中，你可能需要解释这一概念，或分析给定的追踪是否展现了稳定行为。

10. How Sorting Algorithms Are Assessed in Edexcel A-Level | Edexcel A-Level 如何考核排序算法

The Edexcel specification requires you to understand, trace, and compare sorting algorithms. You may be asked to complete a trace table for a specific list, write pseudocode, or discuss the suitability of an algorithm for a given scenario. Questions often test your ability to recognise code snippets and identify the algorithm being used.

Edexcel 大纲要求理解、追踪并比较排序算法。你可能需要为特定列表填写追踪表、编写伪代码，或讨论某算法在给定场景下的适用性。题目经常考察你识别代码片段并判断所用算法的能力。

Key revision points:

关键复习要点：

Memorise the time and space complexities for each algorithm.
记住每种算法的时间与空间复杂度。
Practise tracing bubble sort and insertion sort on small arrays (e.g., [5, 2, 8, 1, 9]) to build muscle memory.
练习在小数组（如 [5, 2, 8, 1, 9]）上追踪冒泡排序和插入排序，以形成肌肉记忆。
Be able to sketch the recursive splitting and merging for merge sort; draw the binary tree of subdivisions.
能够画出归并排序的递归分割与合并过程；画出细分的二叉树。
Understand why quick sort’s worst-case is O(n²) and how pivot selection (e.g., random pivot) mitigates it.
理解为何快速排序的最坏情况是 O(n²)，以及如何通过枢轴选择（如随机枢轴）来缓解。
Compare the use of insertion sort within hybrid sorting algorithms (like Timsort used in Python) for small runs.
比较插入排序在混合排序算法（如 Python 使用的 Timsort）中对小片段的运用。

11. Practice Question and Model Answer | 练习题与示范解答

Question: The array [34, 7, 23, 32, 5, 62] is to be sorted in ascending order using merge sort. Show the step-by-step splitting and merging stages. State the time complexity and explain why merge sort is more suitable than bubble sort for very large arrays.

问题： 数组 [34, 7, 23, 32, 5, 62] 使用归并排序按升序排序。请展示逐步分割与合并的阶段。说明时间复杂度，并解释为什么对于非常大的数组，归并排序比冒泡排序更合适。

Model Answer:

示范解答：

Splitting: [34, 7, 23] and [32, 5, 62]; then split into [34] [7, 23] and [32] [5, 62]; further [7, 23] splits into [7] [23]; [5, 62] splits into [5] [62].
分割： [34, 7, 23] 和 [32, 5, 62]；再分成 [34] [7, 23] 和 [32] [5, 62]；进一步 [7, 23] 分成 [7] [23]；[5, 62] 分成 [5] [62]。
Merging: [7] and [23] → [7, 23]; then [34] and [7, 23] → [7, 23, 34]; similarly [5] and [62] → [5, 62]; then [32] and [5, 62] → [5, 32, 62]; finally merge [7, 23, 34] and [5, 32, 62] → [5, 7, 23, 32, 34, 62].
合并： [7] 和 [23] → [7, 23]；然后 [34] 和 [7, 23] → [7, 23, 34]；类似地 [5] 和 [62] → [5, 62]；然后 [32] 和 [5, 62] → [5, 32, 62]；最后合并 [7, 23, 34] 和 [5, 32, 62] → [5, 7, 23, 32, 34, 62]。
Time complexity: O(n log n) for all cases. Bubble sort has O(n²) worst-case, so on large arrays merge sort is vastly faster because O(n log n) grows much more slowly than O(n²).
时间复杂度：所有情况都是 O(n log n)。冒泡排序最坏情况为 O(n²)，因此在大数组上归并排序要快得多，因为 O(n log n) 比 O(n²) 增长得慢得多。

12. Summary and Final Tips | 总结与最后建议

Mastering sorting algorithms requires both theoretical understanding and hands-on tracing. Focus on the differences between O(n²) and O(n log n) algorithms, and be prepared to justify your choices in an exam context. Always check whether stability or memory usage is a constraint in the question. Regular practice with past papers will build confidence.

掌握排序算法需要理论理解和动手追踪。重点关注 O(n²) 与 O(n log n) 算法的差异，并准备好考试中为你的选择提供理由。始终检查题目中稳定性或内存使用是否为约束条件。定期练习历年真题将建立信心。

Remember, Edexcel often asks you to compare algorithms and suggest the best one for a given situation, so learn the strengths and weaknesses of each sort covered here.

请记住，Edexcel 经常要求比较算法并为给定情况推荐最佳算法，因此要掌握本文所涵盖每种排序的优缺点。

Published by TutorHao | Programming Revision Series | aleveler.com

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

Sorting Algorithms in A-Level Computer Science | A-Level 计算机科学中的排序算法