📚 Sorting Algorithms for A-Level WJEC Computer Science | A-Level WJEC 计算机：排序 考点精讲
Sorting is a fundamental topic in computer science and a key component of the WJEC A-Level specification. Understanding sorting algorithms is essential not only for algorithmic thinking but also for developing skills in complexity analysis and problem decomposition. In this article, we will explore the most important sorting algorithms you need to know for your exam, including bubble sort, insertion sort, merge sort, and quicksort. We will examine how each algorithm works step by step, analyse their time complexities, discuss stability and practical applications, and highlight common pitfalls to avoid. By the end, you will have a thorough revision resource aligned with WJEC requirements, complete with diagrams, comparisons, and exam-style guidance.
排序是计算机科学中的一个基础主题，也是 WJEC A-Level 考试大纲的重要组成部分。理解排序算法不仅对培养算法思维至关重要，还能提升你在复杂度分析和问题分解方面的能力。在本文中，我们将详细讲解 WJEC 考试中你必须掌握的几种核心排序算法，包括冒泡排序、插入排序、归并排序和快速排序。我们会逐步解析每种算法的工作原理，分析它们的时间复杂度，讨论稳定性和实际应用，并指出常见易错点。读完本文，你将拥有一份全面贴合 WJEC 考点的复习资料，内含图解、对比以及应试技巧。
1. Why Sorting Matters in WJEC A-Level | WJEC 考试中排序的重要性
Sorting algorithms are explicitly tested in the WJEC Component 1 and Component 2 written papers. You are expected to be able to trace, explain, and compare the main sorting techniques. Questions often require you to show the step-by-step state of a list after each pass, complete a partially filled trace table, or discuss the efficiency of a given algorithm in terms of its time and space complexity. A deep understanding of sorting also supports topics like searching (binary search requires sorted data), data structures, and algorithmic problem-solving.
排序算法在 WJEC 笔试的卷一和卷二中都有明确考查要求。你需要能够追踪、解释并比较主要的排序方法。考题经常会要求你展示在每一轮排序后列表的状态变化、补全部分填写的追踪表，或者依据时间复杂度和空间复杂度讨论算法的效率。深刻理解排序还能为学习搜索（二分查找需要有序数据）、数据结构和算法求解等主题提供有力支撑。
2. The Basics of Sorting | 排序基础概念
Sorting means arranging a collection of data items in a particular order, usually ascending (smallest first) or descending. The input is typically an array or list of comparable elements such as integers, strings, or records. An in-place sorting algorithm uses a constant amount of extra memory (O(1) space) and rearranges the elements within the original structure. A stable sort preserves the relative order of equal elements; if two items have the same key, their original sequence is maintained. When revising, you must be comfortable with these definitions because WJEC questions may ask you to state whether an algorithm is stable and what ‘in-place’ means.
排序就是将一组数据按照特定的顺序（通常是升序或降序）进行排列。输入通常是一个由可比较元素（如整数、字符串或记录）组成的数组或列表。原地排序算法仅使用常数级额外内存（O(1) 空间）并在原结构内对元素进行重新排列。稳定排序能保持相等元素的相对顺序；若两个元素具有相同的键值，它们在排序后的先后顺序与排序前一致。复习时必须熟练掌握这些定义，因为 WJEC 考题可能会问某个算法是否稳定以及“原地排序”的含义。
3. Bubble Sort – Step-by-Step | 冒泡排序逐步解析
Bubble sort repeatedly steps through the list, compares adjacent items, and swaps them if they are in the wrong order. On each full pass, the largest unsorted element ‘bubbles up’ to its correct position at the end. For an array of n elements, at most n−1 passes are needed. After the ith pass, the last i elements are sorted. The algorithm stops early if no swaps occur in a pass. A typical WJEC trace tables show the array after each pass, and exam questions may ask you to write pseudocode for an optimised version that checks for swaps. The time complexity is O(n²) in the worst and average cases, and O(n) in the best case when the list is already sorted.
冒泡排序会反复遍历列表，比较相邻元素，若顺序不对则交换它们。每完成一轮完整的遍历，当前未排序部分的最大元素就会“冒泡”到它应在的末尾位置。对于含有 n 个元素的数组，最多需要 n−1 轮。第 i 轮之后，末尾 i 个元素已就位。如果某一轮中没有发生任何交换，算法可提前终止。WJEC 典型的追踪表会展示每轮后数组的状态，考题可能要求你写出带有交换标记优化版本的伪代码。其时间复杂度在最坏和平均情况下为 O(n²)，最好情况（列表已有序）下为 O(n)。
pare 5 & 3 swap → [3, 5, 8, 1] → compare 5 & 8 no swap → compare 8 & 1 swap → [3, 5, 1, 8]
一轮冒泡示例（升序）：[5, 3, 8, 1] → 比较 5 和 3 交换 → [3, 5, 8, 1] → 比较 5 和 8 不换 → 比较 8 和 1 交换 → [3, 5, 1, 8]
4. Insertion Sort – Building the Sorted Sequence | 插入排序——构建有序序列
Insertion sort builds the final sorted array one element at a time. It divides the list into a sorted (left) part and an unsorted (right) part. In each iteration, the first element of the unsorted region is taken and inserted into its correct position within the sorted portion, shifting larger elements to the right as needed. This is analogous to sorting playing cards in your hand. Insertion sort is stable and in-place with O(1) extra space. Its time complexity is O(n²) worst/average, but it performs excellently on small or nearly sorted datasets, achieving O(n) in the best case. WJEC may ask you to trace the algorithm through a table showing the sorted sublist growing, or to explain why it is more efficient than bubble sort for nearly sorted data.
插入排序每次构建一个元素，最终得到有序数组。它将列表分为左部已排序区和右部未排序区。每次迭代时，取出未排序区的第一个元素，将其插入到已排序区中的正确位置，必要时将较大元素向右移动。这就像整理手中的扑克牌一样。插入排序是稳定且原地的排序算法，仅需 O(1) 额外空间。其时间复杂度在最坏/平均情况下为 O(n²)，但在小规模或几乎有序的数据集上表现极佳，最好情况可达 O(n)。WJEC 可能会要求你通过表格追踪已排序子列表的增长过程，或解释为何插入排序在处理几乎有序的数据时比冒泡排序更高效。
Insertion trace: [8|, 3, 5] → take 3, insert before 8 → [3, 8|, 5] → take 5, insert between → [3, 5, 8|]
插入排序追踪：[8|, 3, 5] → 取出 3，插入到 8 前 → [3, 8|, 5] → 取出 5，插入到两者之间 → [3, 5, 8|]
5. Merge Sort – Divide and Conquer | 归并排序——分治策略
Merge sort is a classic divide-and-conquer algorithm. It recursively splits the unsorted list into n sublists, each containing one element (which is trivially sorted), then repeatedly merges sublists to produce newly sorted sublists until only one remains. The merging step compares the front elements of two sorted subarrays and picks the smaller one, appending it to the result. This algorithm is stable and has a guaranteed O(n log n) time complexity in all cases, but it requires O(n) additional memory for the temporary arrays during merging, so it is not in-place. WJEC exams often feature tracing diagrams or ask you to complete a merging trace table. You may also need to explain why the space complexity is higher and when that might be a disadvantage (e.g., in memory-constrained embedded systems).
归并排序是一种经典的分治算法。它递归地将未排序列表拆分为 n 个子列表，每个子列表只包含一个元素（自然有序），然后重复合并这些子列表以生成新的有序子列表，直到最终只剩一个有序列表。合并步骤会逐一比较两个有序子数组的首元素，将较小的元素追加到结果中。该算法是稳定的，且在所有情况下都能确保 O(n log n) 的时间复杂度，但在合并过程中需要 O(n) 的额外内存来存储临时数组，因此不是原地排序。WJEC 考试常会给出追踪图示或要求你完成合并追踪表。你可能还需要解释为何它的空间复杂度更高，以及在什么情况下这会成为劣势（例如在内存受限的嵌入式系统中）。
[38, 27] and [43, 3] → split further → merge [27, 38] and [3, 43] → final [3, 27, 38, 43]
归并排序示例：[38, 27, 43, 3] → 拆分为 [38, 27] 和 [43, 3] → 继续拆分 → 合并 [27, 38] 和 [3, 43] → 最终得到 [3, 27, 38, 43]
6. Quicksort – The Pivot-Based Algorithm | 快速排序——基于基准值的算法
Quicksort is another divide-and-conquer algorithm that works by selecting a ‘pivot’ element from the array and partitioning the other elements into two subarrays according to whether they are less than or greater than the pivot. The subarrays are then recursively sorted. The choice of pivot heavily influences performance: always picking the first or last element can lead to O(n²) worst-case behaviour on already sorted data, while a properly chosen pivot (e.g., median-of-three) yields O(n log n) on average. Quicksort is not stable, but it sorts in-place (with O(log n) stack space for recursion). WJEC expects you to understand the partition process in detail, be able to trace the algorithm with a given pivot, and discuss why quicksort is preferred in many standard libraries despite its worst-case O(n²) complexity.
快速排序同样是一种分治算法，其工作原理是从数组中选择一个“基准”（pivot）元素，然后将其他元素按小于基准或大于基准分割成两个子数组。接着递归地对子数组进行排序。基准的选择对性能影响很大：总是选择第一个或最后一个元素可能会在已排序数据上导致 O(n²) 的最坏情况，而合理选择基准（如三数取中法）则平均能实现 O(n log n)。快速排序不稳定，但它是原地排序（递归所需的栈空间为 O(log n)）。WJEC 要求你深入理解分区过程，能够根据给定的基准值追踪该算法，并讨论尽管存在 O(n²) 的最坏情况复杂度，为什么许多标准库仍优先选择快速排序。
4: [5, 2, 8, 1, 4] → after partition: [1, 2, 4, 8, 5], then sort subarrays [1,2] and [8,5]
以 4 为基准的快速排序分区：[5, 2, 8, 1, 4] → 分区后：[1, 2, 4, 8, 5]，然后递归排序子数组 [1,2] 和 [8,5]
7. Comparing Performances – Big O Notation | 性能对比——大 O 表示法
WJEC requires you to compare algorithms using asymptotic notation. Here is a summary table of the key sorting algorithms covered:
WJEC 要求你使用渐近表示法来比较算法。以下是所涉及核心排序算法的汇总表：
| 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 |
| Quicksort | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
For small datasets, insertion sort often outperforms quicksort due to lower constant factors. Merge sort guarantees O(n log n) but uses extra memory, making it unsuitable for extremely large data with tight memory limits. Quicksort’s in-place nature and good cache performance make it the default in many general-purpose libraries. WJEC exam questions can ask you to explain which algorithm you would choose in a given context and justify your decision using complexity arguments.
对于小数据集，插入排序通常比快速排序表现更好，因为它的常数因子更小。归并排序虽然保证 O(n log n)，但会使用额外内存，因此在内存紧张且数据量极大的情况下不适合。快速排序的原地排序特性和良好的缓存性能使其成为许多通用库中的默认选项。WJEC 考题可能会要求你解释在特定场景下会选择哪种算法，并运用复杂度分析来论证你的选择。
8. Stability and Why It Matters | 稳定性及其重要性
Stability is an important concept when sorting records with multiple fields. For example, if a list of students is first sorted by name and then by grade, a stable sort by grade will keep the name order intact among students with the same grade. Merge sort and insertion sort are stable, which is why they are preferred when sorting data that has already been partially ordered by another key. Bubble sort is also stable. Quicksort, however, is not stable because the partitioning step can swap equal elements across the pivot boundary. Knowing the stability characteristic is crucial for WJEC, as you may be asked to suggest a suitable stable sort for a particular task.
在对具有多个字段的记录进行排序时，稳定性是一个重要概念。例如，若学生名单先按姓名排序，再按成绩排序，那么一个稳定的按成绩排序算法会保证相同成绩的学生仍保持原来的姓名顺序。归并排序和插入排序是稳定的，因此当需要对已经按某个键值部分排序的数据进行二次排序时，它们往往成为首选。冒泡排序也是稳定的。然而，快速排序不稳定，因为其分区步骤可能会将相等的元素跨越基准边界进行交换。了解稳定性特征对 WJEC 考试至关重要，因为你可能要为特定任务推荐合适的稳定排序算法。
9. Sorting Algorithm Pseudocode for WJEC | WJEC 考试中的排序伪代码
You should be able to read, interpret, and write pseudocode for the four core algorithms. WJEC often uses a mixture of English-like statements and structured constructs (FOR, WHILE, IF). In bubble sort, the outer loop runs from n−1 down to 1, and the inner loop compares and swaps. For insertion sort, you incrementally shift elements. Merge sort is typically written recursively, and quicksort uses a partition function. Practice writing pseudocode without looking, ensuring you follow the official style shown in past papers. A common mistake is forgetting to mark whether a swap occurred in optimised bubble sort, or omitting the base case in recursive merge sort.
你需要能够阅读、解读并书写四种核心算法的伪代码。WJEC 通常会混合使用类英文语句和结构化结构（FOR、WHILE、IF）。在冒泡排序中，外循环从 n−1 递减至 1，内循环进行比较和交换。插入排序则是逐步移动元素。归并排序通常采用递归写法，快速排序则使用分区函数。练习时在不看资料的情况下默写伪代码，确保符合历年真题中的官方风格。一个常见错误是忘记在优化版冒泡排序中标记是否发生了交换，或者遗漏了递归版归并排序的基例。
10. Tracing Sorting Algorithms – Exam Technique | 排序算法追踪技巧——应试方法
WJEC tracing questions require you to show the contents of the array after each pass or after each major iteration. Always read the question carefully: some ask for the array after each complete pass of bubble sort, while others ask after each swap or each insertion. Draw a table with row headings like "Pass 1", "Pass 2", and columns showing the array indices. Keep your work neat; partial marks are often given for correct intermediate states even if the final answer is wrong. For merge sort, you may need to illustrate the splitting and merging stages using a tree diagram. For quicksort, label the pivot and show the sublist boundaries. Practice with past papers under timed conditions to build speed.
WJEC 的追踪类题目要求你展示每一轮或每次主要迭代后数组的内容。务必仔细审题：有些题目要求展示冒泡排序中每一完整轮次后的数组，而另一些则要求展示每次交换或每次插入后的状态。绘制一张表，行标题为“第1轮”、“第2轮”等，列标题对应数组索引。保持卷面整洁；即使最终答案错误，中间状态的正确展示也常能获得部分分数。对于归并排序，你可能需要用树状图来展示拆分和合并的阶段。对于快速排序，要标注基准值并标明子列表边界。在限时条件下多做真题练习以提升速度。
11. Common Pitfalls and Misconceptions | 常见错误与误区
One common misconception is that quicksort is always O(n log n) – but in its simplest form with a bad pivot it degrades to O(n²). Another is confusing space complexity: insertion sort is in-place with O(1), while merge sort uses O(n) extra memory. Students often mix up stable and unstable algorithms. Also, some believe that bubble sort should always run for n−1 passes, forgetting the early-termination optimisation. When completing trace tables, an off-by-one error in the loop bounds (e.g., comparing up to n instead of n−1) can propagate through the whole answer. Revise these nuances carefully.
一个典型的误区是认为快速排序在任何情况下都是 O(n log n) —— 实际上在其最简单的形式中，若基准选择不当，复杂度会退化到 O(n²)。另一个常见混淆点是空间复杂度：插入排序是原地排序，只需 O(1) 空间，而归并排序需要 O(n) 额外内存。学生也常常混淆稳定与不稳定的算法。此外，一些人认为冒泡排序始终需要执行 n−1 轮，而忘记可以提前终止的优化。在做追踪表时，循环边界上的一处“差一错误”（例如比较到 n 而不是 n−1）可能使整个答案都出错。请仔细复习这些细微差别。
12. Summary and Final Exam Tips | 总结与考前建议
To master the sorting topic for WJEC A-Level Computer Science, you must be able to explain, trace, and compare bubble sort, insertion sort, merge sort, and quicksort. Focus on understanding the mechanism of each algorithm, its time and space complexity in Big O notation, whether it is stable and in-place, and typical scenarios where one is preferred over another. When revising, draw diagrams, write out pseudocode from memory, and complete at least three trace table exercises for each algorithm. In the exam, show all your working – WJEC mark schemes reward method marks even if a final list is incorrect. Finally, remember the comparison table and be ready to justify your choice of algorithm for a given situation using technical reasoning.
要彻底掌握 WJEC A-Level 计算机科目中的排序部分，你必须能够解释、追踪并比较冒泡排序、插入排序、归并排序和快速排序。重点要理解每种算法的机理、用大 O 表示法表示的时间和空间复杂度、算法是否稳定且原地执行，以及在哪些典型场景下某种算法更优。复习时应多画图、默写伪代码，并为每种算法至少完成三道追踪表练习。在考试中，要展示所有解题步骤 —— WJEC 的评分方案对过程分的给予相当宽松，即使最终列表有误也是如此。最后，熟记对比表，并准备好运用技术原理来论证在给定情境下你对算法的选择。
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图