📚 Sorting: IB CCEA Computer Science Revision | 排序：IB CCEA 计算机考点精讲
Sorting algorithms form a fundamental topic in the IB and CCEA Computer Science specifications, testing both theoretical understanding and practical algorithmic thinking. Whether you need to trace a bubble sort, compare the efficiency of merge sort with quick sort, or explain the importance of stability, this guide covers every essential point. We will walk through the most commonly examined algorithms, analyse their time and space complexity, and highlight classic exam pitfalls so that you can approach any sorting question with confidence.
排序算法是 IB 和 CCEA 计算机科学课程中的基础主题，既考查理论理解，也检验算法思维。无论你需要跟踪冒泡排序的过程、比较归并排序与快速排序的效率，还是解释稳定性的重要性，本指南都涵盖了每一个关键点。我们将逐一讲解最常考到的算法，分析它们的时间与空间复杂度，并标出经典的考试陷阱，帮助你自信应对任何排序题。
1. Introduction to Sorting Algorithms | 排序算法概述
Sorting is the process of arranging elements in a list into a specified order – typically ascending (smallest to largest) or descending. In computer science examinations, you are expected to know how common sorting algorithms work, to be able to step through their execution on small datasets, and to discuss their performance characteristics. The core algorithms covered by most IB and CCEA specifications include bubble sort, insertion sort, selection sort, merge sort, and quick sort.
排序是将列表中的元素按指定顺序排列的过程——通常是升序（从小到大）或降序。在计算机科学考试中，你需要了解常见排序算法的工作原理，能够在小数据集上逐步推演其执行过程，并讨论它们的性能特征。大多数 IB 和 CCEA 规范所涵盖的核心算法包括冒泡排序、插入排序、选择排序、归并排序和快速排序。
When comparing algorithms, examiners look for a solid grasp of three key concepts: time complexity (how the number of operations grows with input size n), space complexity (extra memory required), and stability (whether equal elements retain their relative order). You will also encounter questions that ask you to identify an algorithm from a trace, to fill in missing code, or to suggest the most suitable algorithm for a given scenario.
在比较算法时，考官希望看到你对三个关键概念的扎实掌握：时间复杂度（如何随输入规模 n 增长）、空间复杂度（所需额外内存）以及稳定性（相等元素是否保持相对顺序）。你还会遇到要求根据跟踪记录识别算法、填写缺失代码或针对给定场景建议最合适算法的题目。
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 that the list is sorted. After the first complete pass, the largest element has "bubbled up" to its correct position at the end; the second pass places the second-largest element, and so on. For an array of n elements, the algorithm can require up to n−1 passes.
冒泡排序反复遍历列表，比较相邻元素，如果顺序错误则交换它们。这一遍历过程会重复进行，直到不需要任何交换为止，表明列表已排序。第一轮完整遍历后，最大元素会“冒泡”到末尾的正确位置；第二轮遍历将次大元素放置到位，依此类推。对于包含 n 个元素的数组，该算法最多需要 n−1 轮遍历。
- Bubble sort is simple to implement but inefficient on large lists – its worst-case and average time complexity is O(n²).
- 冒泡排序实现简单，但在大数据集上效率低下——最坏情况和平均时间复杂度为 O(n²)。
- It is stable because equal elements are never swapped past one another; they remain in their original relative order.
- 它是稳定的，因为相等的元素永远不会相互跳过，它们保持原始的相对顺序。
- The smallest element moves very slowly toward the beginning (often called "rabbits and turtles": large elements move quickly, small ones move slowly).
- 最小元素向开头的移动速度非常缓慢（常被称为“兔子和乌龟”：大元素移动得快，小元素移动得慢）。
- An optimised version stops early if no swaps occur during a pass, which yields a best-case O(n) time for an already sorted list.
- 优化版本在某一轮遍历中没有发生交换时会提前终止，对已排序列表可以得到最好情况 O(n) 时间。
3. Insertion Sort | 插入排序
Insertion sort builds the final sorted array one element at a time. It picks the next unsorted element and inserts it into its correct position within the already sorted portion of the list by shifting larger elements one place to the right. This is the algorithm many people use when sorting a hand of playing cards.
插入排序一次建立一个元素，逐步构建最终的已排序数组。它取出下一个未排序元素，通过将较大的元素向右移动一位，将其插入到列表已排序部分的正确位置。这是许多人在整理手中扑克牌时使用的算法。
- Insertion sort has average and worst-case time complexity of O(n²), but it performs very efficiently on small or nearly sorted data.
- 插入排序的平均和最坏情况时间复杂度为 O(n²)，但在数据量小或几乎已排序的情况下性能非常好。
- Its best-case time complexity is O(n) when the input is already sorted; the inner shifting loop never executes.
- 当输入已排序时，其最好情况时间复杂度为 O(n)，内层移动循环不会执行。
- Insertion sort is stable – when inserting an element, you stop at the position after all equal elements, preserving their relative order.
- 插入排序是稳定的——插入元素时，在遇到所有相等元素之后的位置停止，从而保持相对顺序。
- It is an in-place algorithm, requiring only O(1) constant extra space aside from the input array.
- 它是一种原地算法，除了输入数组外仅需要 O(1) 的常量额外空间。
4. Selection Sort | 选择排序
Selection sort divides the list into a sorted sublist (built from left to right) and an unsorted sublist. On each pass, it selects the smallest (or largest) element from the unsorted portion and swaps it with the leftmost unsorted element, moving the boundary between the sorted and unsorted parts one position to the right.
选择排序将列表分为已排序子列表（从左到右构建）和未排序子列表。每一轮遍历中，它从未排序部分选出最小（或最大）元素，将其与最左边的未排序元素交换，然后将已排序和未排序部分的分界线向右移动一个位置。
- Selection sort always performs exactly n−1 swaps, making it useful when write operations are expensive, but its O(n²) time complexity limits its use on large lists.
- 选择排序总是恰好执行 n−1 次交换，当写操作开销很大时它较为有用，但其 O(n²) 的时间复杂度限制了在大列表上的使用。
- It is not stable by default because a swap can change the relative order of equal elements. For example, swapping the minimal element past an equal element can invert their order.
- 默认情况下它不稳定，因为一次交换可能改变相等元素的相对顺序。例如，将最小元素与一个相等元素交换时可能导致顺序颠倒。
- Even on a sorted array, selection sort still performs all comparisons, giving it a consistent O(n²) behaviour regardless of input order.
- 即使在已排序的数组上，选择排序依然会执行所有比较操作，因此无论输入顺序如何，其性能都稳定为 O(n²)。
5. Merge Sort | 归并排序
Merge sort is a divide-and-conquer algorithm. It recursively splits the unsorted list into n sublists, each containing one element (a list of one element is considered sorted). Then it repeatedly merges sublists to produce new sorted sublists until there is only one sublist remaining – the fully sorted list.
归并排序是一种分治算法。它递归地将未排序列表拆分成 n 个子列表，每个子列表包含一个元素（单元素列表被视为已排序）。然后，它不断地归并子列表以生成新的已排序子列表，直到只剩下一个子列表为止——即完全排序后的列表。
- The merging of two sorted sublists is the key operation: compare the smallest elements of each sublist, place the smaller into the result, and advance. This preserves stability.
- 归并两个已排序子列表是关键操作：比较每个子列表的最小元素，将较小的放入结果中，并前进。这保持了稳定性。
- Merge sort has a guaranteed time complexity of O(n log n) in all cases – best, average, and worst.
- 归并排序在所有情况下（最好、平均、最坏）都能保证 O(n log n) 的时间复杂度。
- Its main drawback is the additional O(n) space required for temporary arrays during merging, meaning it is not in-place.
- 其主要缺点是在归并过程中需要额外的 O(n) 空间用于临时数组，因此它不是原地算法。
- Because the merging process does not reorder equal elements from the left and right sublists, merge sort is stable.
- 由于归并过程不会对左右子列表中相等的元素重新排序，归并排序是稳定的。
6. Quick Sort | 快速排序
Quick sort also uses the divide-and-conquer strategy. It selects a 'pivot' element from the array and partitions the other elements into two sub-arrays: those less than the pivot and those greater than the pivot. The sub-arrays are then recursively sorted. The key to quick sort's performance lies in efficient partitioning and good pivot selection.
快速排序同样采用分治策略。它从数组中选取一个“基准”（pivot）元素，并将其他元素划分为两个子数组：小于基准的元素和大于基准的元素。然后递归地对子数组进行排序。快速排序性能的关键在于高效的分区操作和良好的基准选择。
- The worst-case time complexity is O(n²), occurring when the pivot is always the smallest or largest element (e.g., already sorted data with a bad pivot choice).
- 最坏情况时间复杂度为 O(n²)，当基准始终是最小或最大元素时可发生（例如，在已排序数据中选择了糟糕的基准）。
- With a good pivot (e.g., median or random), average time complexity is O(n log n), making it one of the fastest general-purpose sorts.
- 若选择良好的基准（例如中位数或随机选取），平均时间复杂度为 O(n log n)，使其成为最快的通用排序算法之一。
- Quick sort is normally not stable because the partitioning step can swap equal elements out of their relative order.
- 快速排序通常不稳定，因为分区步骤可能将相等元素交换出原有的相对顺序。
- It operates in-place, requiring only O(log n) space for the recursion stack on average, which makes it memory-efficient.
- 它是原地操作的，平均只需 O(log n) 的递归栈空间，因此内存利用效率高。
7. Algorithm Complexity Basics | 算法复杂度基础
Examiners expect you to use big-O, big-Omega, and big-Theta notation appropriately when discussing sorting algorithms. For CCEA and IB papers, you need to describe how the number of key comparisons and data swaps scales with input size n under different circumstances.
考官期望你在讨论排序算法时能恰当地使用大O、大Ω和大Θ符号。对于 CCEA 和 IB 试卷，你需要描述在输入规模 n 下，关键比较次数和数据交换次数在不同情况下如何增长。
| Algorithm | Best Case | Average Case | Worst Case | Space |
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) |
| Selection 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) |
up to n times, we get approximately n × n operations. Logarithmic behaviour arises when the problem is halved repeatedly, as in merge sort and quick sort.
理解为什么平方级算法的时间复杂度是 O(n²) 有助于回答跟踪题：外层循环运行 n 次，内层循环最多运行 n 次，于是就得到大约 n × n 次操作。对数行为出现在问题被反复折半时，如归并排序和快速排序。
8. Stability of Sorting Algorithms | 排序算法的稳定性
A sorting algorithm is stable if it preserves the relative order of items with equal keys. Stability matters when data has multiple fields and you need to sort by one field while retaining the order established by a previous sort. For example, if you first sort student records by name and then sort stably by grade, students with the same grade will remain in alphabetical order.
如果排序算法能保持相等键值项的原有相对顺序，它就是稳定的。当数据有多个字段，而你需要先按一个字段排序，同时保留之前排序已建立的顺序时，稳定性就很重要。例如，先按姓名对学生记录排序，再按成绩进行稳定排序，成绩相同的学生依然会保持字母顺序。
- Bubble sort, insertion sort, and merge sort are inherently stable when implemented carefully.
- 冒泡排序、插入排序和归并排序在小心实现时是天生稳定的。
- Selection sort is generally unstable because swapping the minimum element over a distance can disturb the order of equals.
- 选择排序通常不稳定，因为长距离交换最小元素可能扰乱相等元素的顺序。
- Quick sort is typically unstable due to the partitioning step, though stable versions exist at the cost of extra memory.
- 快速排序通常因分区步骤而不稳定，不过存在以额外内存为代价的稳定版本。
- In exam short-answer questions, you may be asked to identify which of two algorithms would maintain the original order of duplicate keys – this is a cue to discuss stability.
- 在考试简答题中，你可能被要求判断两个算法中哪个能保持重复键的原始顺序——这是在提示你讨论稳定性。
9. Comparing Sorting Algorithms | 排序算法比较
ten best handled by insertion sort due to its low overhead. For large datasets, merge sort or quick sort are preferred because of their O(n log n) performance. If the data is nearly sorted to begin with, insertion sort can outperform even merge sort in practice.
为特定场景选择正确的排序算法是常见的考试任务。小数据集（n ≤ 50）通常用插入排序处理最好，因为它开销低。对于大数据集，归并排序或快速排序由于 O(n log n) 的性能而被优先选择。如果数据几乎已经排好序，插入排序在实际中甚至可能胜过归并排序。
- Merge sort is the safest choice when worst-case O(n log n) performance must be guaranteed, and when stability is required.
- 当归并排序必须保证最坏情况 O(n log n) 的性能且需要稳定性时，它是最安全的选择。
- Quick sort is generally faster in practice due to smaller constant factors but carries the O(n²) worst-case risk; good pivot strategies mitigate this.
- 快速排序由于较小的常数因子在实践中通常更快，但存在 O(n²) 的最坏情况风险；良好的基准选择策略能缓解这一问题。
- Selection sort makes the fewest swaps, making it valuable when writing to memory is costly, but its comparison count is always high.
- 选择排序的交换次数最少，当内存写入代价高昂时具有价值，但其比较次数始终很高。
- For linked lists, merge sort is particularly well-suited because merging does not require random access, whereas quick sort needs efficient random access for partitioning.
- 对于链表，归并排序尤其合适，因为归并不需要随机访问，而快速排序在分区时需要高效的随机访问。
10. Tracing and Pseudocode Skills | 跟踪与伪代码技巧
CCEA and IB exams frequently ask you to trace a sorting algorithm on a small array, step by step. You must be able to write the state after each pass, showing exactly which elements have been compared and swapped. This requires a solid mental model of how each algorithm's pointers move.
CCEA 和 IB 考试经常要求你逐步跟踪一个小数组的排序算法。你必须能够写出每一轮遍历后的状态，准确显示哪些元素被比较和交换。这需要对每种算法的指针移动方式有清晰的心智模型。
- When tracing bubble sort, focus on the inner loop that goes from the start to the unsorted boundary. Mark the elements that have already bubbled to their final positions.
- 跟踪冒泡排序时，关注内层循环从开头到未排序边界的过程。标注已经冒泡到最终位置的元素。
- For insertion sort, show the sorted portion on the left and the element being inserted; demonstrate shifting of larger elements to the right.
- 对于插入排序，展示左侧的已排序部分以及正在插入的元素；演示较大元素右移的过程。
- In merge sort traces, draw the recursive tree of divisions and show the merge steps with temporary arrays.
- 在归并排序跟踪中，画出递归分割树，并展示带临时数组的归并步骤。
- Quick sort traces must highlight the pivot, the partitioning process, and the two sub-arrays before recursion.
- 快速排序跟踪必须突出基准、分区过程以及递归前的两个子数组。
- Practise writing algorithm fragments in pseudocode, especially the swap operation and nested loops.
- 练习用伪代码编写算法片段，尤其是交换操作和嵌套循环。
11. Common Pitfalls and Exam Tips | 常见陷阱与考试技巧
Many marks are lost through small mistakes in complexity statements or misreading the direction of a traversal. Always note whether the algorithm runs left-to-right or right-to-left, and whether the inner loop starts at 0 or at a boundary that shrinks. Remember that best-case O(n) for insertion and bubble sort only applies to specially optimised versions that detect an early stop.
许多分数都是在复杂度表述上的小错误或误读遍历方向中丢失的。务必注意算法是从左向右还是从右向左运行，内层循环是从 0 开始还是从逐渐缩小的边界开始。记住，插入排序和冒泡排序的 O(n) 最好情况只适用于检测提前终止的特殊优化版本。
- Do not confuse the number of passes with the number of comparisons; a single pass may contain multiple comparisons.
- 不要混淆遍历次数与比较次数；一次遍历可能包含多次比较。
- When stating space complexity, distinguish between auxiliary extra space and total space. In-place means O(1) extra space.
- 在表述空间复杂度时，要区分额外辅助空间和总空间。原地算法意味着 O(1) 额外空间。
- If a question says 'suggest one advantage of merge sort over quick sort', mention guaranteed O(n log n) time and stability.
- 如果题目说“请提出归并排序相对于快速排序的一个优点”，要提到保证 O(n log n) 的时间和稳定性。
- Always read the question carefully: it might ask for the state after three passes, not after the entire sort is finished.
- 仔细审题：题目可能要求写出三轮遍历后的状态，而非整个排序完成后的状态。
- Use the correct notation: write O(n log n), not O(n*log n); use the log with assumed base 2 in computer science contexts.
- 使用正确的符号：写作 O(n log n)，而非 O(n*log n)；在计算机科学语境中，对数默认以 2 为底。
12. Summary and Quick Reference | 总结与速查表
Mastering sorting algorithms is not just about memorising pseudocode—it is about developing the ability to choose, compare, and trace algorithms under exam conditions. A strong candidate can explain why quick sort is usually faster but why merge sort is safer, and can identify stability issues instantly. Use the comparison table below as a quick revision reference before your test.
掌握排序算法不仅仅是记忆伪代码——而是要培养在考试条件下选择、比较和跟踪算法的能力。优秀的考生会解释为什么快速排序通常更快，而归并排序更安全，并能瞬间识别稳定性问题。考前用下面的比较表作为快速复习参考。
| Property | Bubble | Insertion | Selection | Merge | Quick |
| Worst Time | O(n²) | O(n²) | O(n²) | O(n log n) | O(n²) |
| Avg Time | O(n²) | O(n²) | O(n²) | O(n log n) | O(n log n) |
| Space | O(1) | O(1) | O(1) | O(n) | O(log n) |
| Stable? | Yes | Yes | No | Yes | No |
| Method | Exchanging | Insertion | Selection | Merging | Partitioning |
Keep this guide handy and test yourself by tracing a mixed dataset with each algorithm. The more you practise, the more automatic the patterns become, allowing you to secure high marks in the sorting section of your IB or CCEA Computer Science paper.
把这份指南放在手边，用一个混合数据集逐一跟踪每种算法来测试自己。练习得越多，这些模式就越能成为本能，让你在 IB 或 CCEA 计算机科学试卷的排序部分稳拿高分。
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图