📚 Sorting Algorithms Exam Focus for IB & WJEC Computer Science | IB WJEC 计算机：排序 考点精讲
Sorting algorithms are fundamental to computer science and appear consistently in IB and WJEC exam papers. Understanding how they work, their time complexities, and their practical trade-offs is essential for both paper-based tracing questions and coding exercises. This revision guide covers the core sorting algorithms you need to know, comparing their mechanisms, efficiency, stability, and use cases, all presented with clear English and Chinese parallel explanations to support bilingual learners.
排序算法是计算机科学的基础，在 IB 和 WJEC 试卷中经常出现。理解它们的工作原理、时间复杂度以及实际权衡是做好纸上追踪题和编程练习的关键。这份复习指南涵盖你必须掌握的核心排序算法，比较它们的机制、效率、稳定性和使用场景，所有内容均以清晰的英中对照解释呈现，以支持双语学习者。
1. Introduction to Sorting | 排序简介
Sorting refers to arranging a list of items into a specific order, typically ascending or descending, based on a key field. Efficient sorting is crucial for optimizing other algorithms, such as searching, and for organising data for human readability or further processing.
排序是指将一组条目按照特定顺序（通常是升序或降序）排列，通常基于某个关键字段。高效的排序对于优化其他算法（如搜索）以及组织数据以供人阅读或进一步处理至关重要。
In both IB and WJEC syllabi, you are expected to be able to trace step-by-step execution of sorting algorithms on small data sets, explain their logic, and evaluate their performance using Big O notation. Common types include comparison-based sorts like bubble sort, selection sort, insertion sort, merge sort, and quick sort.
在 IB 和 WJEC 教学大纲中，你需要能够在小数据集上逐步追踪排序算法的执行，解释其逻辑，并使用大 O 表示法评估其性能。常见的类型包括基于比较的排序，如冒泡排序、选择排序、插入排序、归并排序和快速排序。
2. Bubble Sort | 冒泡排序
Bubble sort repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, indicating the list is sorted. After each complete pass, the largest unsorted element ‘bubbles up’ to its correct position at the end.
冒泡排序反复遍历列表，比较相邻元素，如果顺序错误则交换它们。遍历列表的过程会重复进行，直到不需要任何交换，这表示列表已排序。每完成一次完整遍历，最大的未排序元素就会“冒泡”到末尾的正确位置。
Example with list [5, 3, 8, 1]:
First pass: (5,3) → swap → [3,5,8,1]; (5,8) → no swap; (8,1) → swap → [3,5,1,8]. Second pass: (3,5) → no swap; (5,1) → swap → [3,1,5,8]; (5,8) → no swap. Third pass: (3,1) → swap → [1,3,5,8]; sorted.
示例列表 [5, 3, 8, 1]：
第一趟：(5,3) → 交换 → [3,5,8,1]；(5,8) → 不交换；(8,1) → 交换 → [3,5,1,8]。第二趟：(3,5) → 不交换；(5,1) → 交换 → [3,1,5,8]；(5,8) → 不交换。第三趟：(3,1) → 交换 → [1,3,5,8]；排序完成。
Bubble sort has average and worst-case time complexity of O(n²), making it impractical for large datasets. It is, however, easy to implement and can be detected early if the list becomes sorted before completing all passes (optimised version).
冒泡排序的平均和最坏情况时间复杂度为 O(n²)，因此不适合大型数据集。然而，它易于实现，并且如果列表在完成所有遍历之前就已排序（优化版本），则可以提前检测到。
3. Selection Sort | 选择排序
Selection sort divides the input list into two parts: a sorted sublist and an unsorted sublist. It repeatedly finds the smallest (or largest) element from the unsorted sublist and swaps it with the leftmost unsorted element, moving the boundary of the sorted sublist one element to the right.
选择排序将输入列表分为两部分：已排序子列表和未排序子列表。它反复从未排序子列表中找出最小（或最大）元素，并将其与最左边的未排序元素交换，将已排序子列表的边界向右移动一个元素。
Consider list [7, 4, 9, 2]:
Step 1: min is 2, swap with 7 → [2, 4, 9, 7]; Step 2: min in [4,9,7] is 4, already in position; Step 3: min in [9,7] is 7, swap with 9 → [2,4,7,9]; sorted.
考虑列表 [7, 4, 9, 2]：
步骤 1：最小值为 2，与 7 交换 → [2, 4, 9, 7]；步骤 2：[4,9,7] 中最小值为 4，已在位；步骤 3：[9,7] 中最小值为 7，与 9 交换 → [2,4,7,9]；排序完成。
The algorithm always performs O(n²) comparisons, regardless of initial order. It makes at most O(n) swaps, meaning it can be useful when write operations are expensive. However, it is not stable.
该算法始终进行 O(n²) 次比较，无论初始顺序如何。它最多进行 O(n) 次交换，这意味着在写操作代价高昂时可能有用。然而，它是不稳定的。
4. Insertion Sort | 插入排序
Insertion sort builds the final sorted array one item at a time, taking each element from the unsorted part and inserting it into its correct position within the sorted part by shifting larger elements to the right. It mimics how you might sort playing cards in your hand.
插入排序每次构建一个有序数组，它从未排序部分取出每个元素，并通过将较大元素向右移动，将其插入到已排序部分的正确位置。这类似于你手中整理扑克牌的方式。
For list [9, 5, 1, 4]:
Start with 9 (sorted). Take 5: insert before 9 → [5,9,1,4]; take 1: insert at front → [1,5,9,4]; take 4: insert between 1 and 5 → [1,4,5,9].
对于列表 [9, 5, 1, 4]：
以 9 开始（已排序）。取出 5：插入到 9 前 → [5,9,1,4]；取出 1：插入到最前面 → [1,5,9,4]；取出 4：插入到 1 和 5 之间 → [1,4,5,9]。
Insertion sort has O(n²) average and worst-case complexity, but it performs well on small or nearly sorted lists (O(n) best case). It is stable and in-place, often used as the base case for more advanced algorithms like quicksort or within hybrid sorts (e.g., Timsort).
插入排序的平均和最坏情况复杂度为 O(n²)，但在小型或近乎排序的列表上表现良好（最佳情况 O(n)）。它是稳定且原地排序，常被用作更高级算法（如快速排序）的基本情形，或用于混合排序（如 Timsort）。
5. Merge Sort | 归并排序
Merge sort is a divide-and-conquer algorithm that splits the list into two halves, recursively sorts each half, and then merges the two sorted halves to produce the fully sorted list. The merge step compares the smallest remaining elements of each half and appends the smaller to the result.
归并排序是一种分治算法，将列表分成两半，递归地对每一半进行排序，然后合并两个已排序的半列表以生成完全排序的列表。合并步骤会比较每一半中剩余的最小元素，并将较小的元素添加到结果中。
Example: [6, 3, 8, 5, 2, 7]
Split: [6,3,8] and [5,2,7]; further split each until single elements: [6], [3,8] → [3], [8] etc. Merge: [3] and [8] → [3,8]; then with [6] → [3,6,8]. Similarly [2,5,7]. Final merge: compare 3,2 → take 2; then 3,5 → take 3; etc. → [2,3,5,6,7,8].
示例：[6, 3, 8, 5, 2, 7]
拆分：[6,3,8] 和 [5,2,7]；继续拆分每个部分直到单个元素：[6]、[3,8] → [3]、[8] 等。合并：[3] 和 [8] → [3,8]；然后与 [6] → [3,6,8]。同样地 [2,5,7]。最终合并：比较 3 和 2 → 取 2；然后 3 和 5 → 取 3；等等 → [2,3,5,6,7,8]。
Merge sort guarantees O(n log n) complexity in all cases, making it efficient for large datasets. However, it requires O(n) additional memory space for the merging process, which can be a drawback in memory-constrained environments. It is a stable sort.
归并排序在所有情况下都保证 O(n log n) 复杂度，因此对大型数据集非常高效。然而，合并过程需要 O(n) 的额外内存空间，这在内存受限的环境中可能是一个缺点。它是一种稳定的排序。
6. Quick Sort | 快速排序
Quick sort also uses divide-and-conquer. It selects a ‘pivot’ element and partitions the array into two sub-arrays: elements less than the pivot and elements greater than the pivot. It then recursively sorts the sub-arrays. The pivot ends up in its final sorted position.
快速排序也使用分治法。它选择一个“枢轴”元素，并将数组划分为两个子数组：小于枢轴的元素和大于枢轴的元素。然后递归地对子数组进行排序。枢轴最终位于其最终排序位置。
Using list [10, 7, 8, 9, 1, 5] with pivot 5 (last element):
Partition: elements less than 5: [1]; elements greater: [10,7,8,9]. Put pivot between → [1,5,10,7,8,9]. Recursively sort left [1] (done); right [10,7,8,9] pick pivot 9, partition → [7,8,10], etc. Final sorted list [1,5,7,8,9,10].
使用列表 [10, 7, 8, 9, 1, 5]，以 5 为枢轴（末尾元素）：
划分：小于 5 的元素：[1]；大于 5 的元素：[10,7,8,9]。将枢轴放在中间 → [1,5,10,7,8,9]。递归排序左边 [1]（完成）；右边 [10,7,8,9] 选择枢轴 9，划分 → [7,8,10] 等。最终排序列表 [1,5,7,8,9,10]。
Average-case time is O(n log n), but worst-case is O(n²) when pivot selection is poor (e.g., already sorted array). Good pivot strategies (median-of-three, random) help avoid worst-case. Quicksort is often faster in practice due to better cache performance and low overhead. It is not stable, but in-place variant exists.
平均情况时间为 O(n log n)，但当枢轴选择不佳时（例如，已排序数组），最坏情况为 O(n²)。良好的枢轴策略（三数取中、随机）有助于避免最坏情况。由于更好的缓存性能和低开销，快速排序在实践中通常更快。它是不稳定的，但存在原地排序的变体。
7. Time Complexity Comparison | 时间复杂度对比
Understanding Big O notation for sorting algorithms is vital for exam comparisons and justifying algorithm choice. Below is a summary of time complexities for the discussed algorithms.
理解排序算法的大 O 表示法对于考试中的比较和算法选择的论证至关重要。以下是所讨论算法的时间复杂度总结。
| Algorithm / 算法 | Best / 最佳 | Average / 平均 | Worst / 最差 | Space / 空间 |
|---|---|---|---|---|
| Bubble Sort / 冒泡排序 | O(n) | O(n²) | O(n²) | O(1) |
| Selection 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)* / O(n) |
*Quicksort space complexity for the call stack; O(log n) for in-place version with tail recursion, O(n) worst-case stack space.
*快速排序的空间复杂度用于调用栈；原地版本使用尾递归为 O(log n)，最坏情况栈空间为 O(n)。
Notice that quadratic sorts are only suitable for small n (typically n < 100), while O(n log n) sorts are preferred for larger datasets. Merge sort's guarantee makes it a safe choice when consistent performance is needed, but quicksort's average speed often makes it the library default.
请注意，平方级别的排序仅适用于小型 n（通常 n < 100），而 O(n log n) 排序更适用于大型数据集。归并排序的保证使其在需要稳定性能时成为可靠选择，但快速排序的平均速度常使其成为库的默认选择。
8. Stability of Sorting Algorithms | 排序算法的稳定性
A sorting algorithm is stable if it preserves the relative order of records with equal keys. Stability matters when sorting by multiple attributes (e.g., sort by surname, then by age).
如果排序算法保留了具有相等键的记录的相对顺序，则它是稳定的。当按多个属性排序时（例如，先按姓氏排序，再按年龄排序），稳定性很重要。
Stable sorts: Bubble sort, insertion sort, merge sort (if merge merges equal keys from left first). Unstable sorts: Selection sort (swapping can change order), quicksort (partition step does not preserve order), heap sort. For WJEC and IB, you may be asked to identify if a given algorithm is stable and explain why with a counterexample.
稳定排序：冒泡排序、插入排序、归并排序（如果合并时优先合并左侧的相等键）。不稳定排序：选择排序（交换可能改变顺序）、快速排序（划分步骤不保留顺序）、堆排序。在 WJEC 和 IB 中，可能会要求你判断给定算法是否稳定，并用反例解释原因。
9. In-place Sorting | 原地排序
An in-place sorting algorithm uses only a constant amount (O(1)) of extra memory beyond the input array. In-place algorithms can be crucial when memory is limited.
原地排序算法仅使用常量（O(1)）数量级的额外内存，不包括输入数组所占空间。当内存有限时，原地算法至关重要。
Bubble, selection, and insertion sorts are in-place. They modify the original list directly. Merge sort is not in-place in its standard form because it requires auxiliary arrays. Quicksort can be implemented in-place, though the recursion stack uses O(log n) space. Knowing this distinction helps in selecting suitable algorithms for embedded systems or large data on disk.
冒泡排序、选择排序和插入排序是原地排序，它们直接修改原始列表。标准的归并排序不是原地排序，因为它需要辅助数组。快速排序可以实现为原地排序，尽管递归栈使用 O(log n) 的空间。了解这一区别有助于在嵌入式系统或磁盘上的大数据中选择合适的算法。
10. Choosing the Right Sort | 选择合适的排序算法
In exams and real-world programming, you must justify your choice of sorting algorithm based on the data and constraints. Consider the following factors: size of input, whether the data is partially sorted, memory limitations, stability requirements, and whether worst-case performance guarantee is needed.
在考试和实际编程中，你必须根据数据和限制条件来证明所选择的排序算法。考虑以下因素：输入的大小、数据是否部分有序、内存限制、稳定性要求，以及是否需要最坏情况下的性能保证。
- Small datasets (n < 30): Insertion sort is often fastest due to low overhead.| 小数据集（n < 30）：插入排序由于开销低通常最快。
- Nearly sorted data: Insertion sort or optimised bubble sort works well.| 几乎有序的数据：插入排序或优化后的冒泡排序表现良好。
- Large datasets with memory constraints: Heapsort or in-place quicksort.| 内存受限的大数据集：堆排序或原地快速排序。
- Stable sort required: Merge sort or insertion sort, not quicksort (unstable).| 需要稳定排序：归并排序或插入排序，而非快速排序（不稳定）。
- Guaranteed O(n log n): Merge sort or heapsort.| 保证 O(n log n)：归并排序或堆排序。
IB questions might ask you to analyse an unfamiliar scenario, while WJEC papers may give you a partially filled trace table and ask you to complete it, then evaluate efficiency. Practise both.
IB 题目可能要求你分析一个不熟悉的场景，而 WJEC 试卷可能会给出部分填充的追踪表，要求你完成它，然后评估效率。两者都要练习。
11. Key Exam Tips | 考试要点提示
When tackling sorting questions, remember to: (1) Clearly label each pass or recursion level in tracing. (2) Use correct terminology (pass, pivot, merge, partition). (3) Compare algorithms using Big O notation precisely — quoting best, average, worst cases. (4) If asked to write code, pay attention to loop boundaries and termination conditions. (5) For IB Paper 1 style questions, be ready to explain why one sort is preferred over another in a given context.
在处理排序题目时，请记住：（1）在追踪中清晰地标注每一趟或递归层级。（2）使用正确的术语（趟、枢轴、合并、划分）。（3）精确使用大 O 表示法比较算法——引用最佳、平均、最坏情况。（4）如果要求编写代码，请注意循环边界和终止条件。（5）对于 IB Paper 1 风格的题目，要准备好解释为什么在特定上下文中某一种排序优于另一种。
A common pitfall is confusing O(n) with O(n log n) and underestimating the impact of constant factors. Another is forgetting that quicksort has O(n²) worst case, while merge sort is always O(n log n). Avoid relying on memorisation alone; practice drawing the process for small arrays to internalise the logic.
一个常见的误区是混淆 O(n) 与 O(n log n)，以及低估常数因子的影响。另一个是忘记快速排序的最坏情况为 O(n²)，而归并排序始终为 O(n log n)。不要仅依赖记忆；通过绘制小型数组的处理过程来内化逻辑。
Use previous exam papers to trace both simple and complex examples. Being fluent in tracing bubble, insertion, selection, merge, and quicksort will give you confidence to handle any sorting-related question on the IB and WJEC exams.
使用往年真题来追踪简单和复杂的示例。熟练追踪冒泡、插入、选择、归并和快速排序将使你自信地应对 IB 和 WJEC 考试中的任何排序相关问题。
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导