📚 IB & CIE Computer Science: Sorting – Key Points Explained | IB CIE 计算机：排序考点精讲
Sorting algorithms form a cornerstone of any computer science syllabus. Whether you are studying IB Diploma or Cambridge International A-Level, a solid grasp of common sorting methods – their mechanics, efficiency, and behaviour – is essential for both written papers and practical problem-solving. This revision guide unpacks the key sorting algorithms, compares their complexities, and highlights the exam-style points that frequently trap students.
排序算法是任何计算机科学课程的基础。无论你学习的是IB文凭课程还是剑桥国际A-Level，扎实掌握常见排序方法（包括它们的机制、效率和行为）对于笔试和实践问题的解决都至关重要。这份复习指南将拆解关键排序算法，比较它们的复杂度，并突出考卷中经常让学生丢分的考点。
1. What is Sorting? | 什么是排序？
Sorting is the process of arranging a collection of data elements in a particular order – typically ascending or descending – based on a defined key. Efficient sorting reduces the complexity of later operations such as searching, merging, and reporting.
排序是按照特定顺序（通常是升序或降序）排列数据元素集合的过程，基于一个定义的键。高效的排序可以降低后续操作（如搜索、合并和报告）的复杂度。
In board exams, you are expected to trace and evaluate algorithms on small datasets, identify stable vs unstable sorts, and compare time and space complexity using Big O notation.
在考试中，你需要能够在小数据集上跟踪和评估算法，识别稳定排序与非稳定排序，并使用大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 largest unsorted element "bubbles up" to its correct position at the end of each pass.
冒泡排序反复遍历列表，比较相邻元素，如果顺序错误就交换它们。每一轮遍历后，最大的未排序元素会 "冒泡" 到正确的位置，即列表的末尾。
After the first pass, the last element is guaranteed to be in its final place. The algorithm then performs a shorter pass on the remaining unsorted portion until no swaps occur.
第一轮遍历后，最后一个元素必然处于最终位置。然后算法在剩余的未排序部分进行更短的遍历，直到没有交换发生。
Bubble sort has a worst-case and average time complexity of O(n²), where n is the number of items. The best case (already sorted list) is O(n) if an optimised flag detects no swaps early.
冒泡排序的最坏情况和平均时间复杂度是 O(n²)，其中 n 是数据项的数量。如果采用优化标志提前发现没有交换，最佳情况（列表已排序）的时间复杂度为 O(n)。
Space complexity is O(1) because it operates in-place, needing only a single temporary variable for swapping. Bubble sort is stable – equal elements retain their relative order.
空间复杂度为 O(1)，因为它是原地排序，只需要一个临时变量用于交换。冒泡排序是稳定的：相等的元素会保持原来的相对顺序。
3. Insertion Sort | 插入排序
Insertion sort builds the final sorted array one element at a time. It takes each element from the unsorted part and inserts it into its correct position within the sorted portion by shifting larger elements to the right.
插入排序一次一个元素地建立最终排序数组。它从无序部分取出每个元素，通过将较大元素向右移动，把该元素插入到有序部分的合适位置。
The algorithm starts by assuming the first element is sorted. For each next element, it compares backwards and shifts until the correct insertion point is found.
算法一开始假设第一个元素是有序的。对于接下来每个元素，它向后比较并移动，直到找到正确的插入点。
Average and worst-case time complexity are O(n²), while the best case (already sorted) is O(n) because each element is simply compared once. This makes insertion sort efficient for small or nearly sorted datasets.
平均和最坏情况时间复杂度是 O(n²)，而最佳情况（已排序）为 O(n)，因为每个元素只需要比较一次。这使得插入排序对于小型或近乎有序的数据集非常高效。
Insertion sort is stable and has O(1) space complexity. In exams, you may be asked to trace its behaviour on an array or explain why it performs well on partially ordered lists.
插入排序是稳定的，空间复杂度为 O(1)。考试中可能会要求你跟踪其数组行为，或解释为何它在部分有序列表上表现良好。
4. Selection Sort | 选择排序
Selection sort divides the list into a sorted prefix and an unsorted suffix. In each pass, it selects the smallest (or largest) element from the unsorted part and swaps it with the leftmost unsorted element.
选择排序将列表划分为一个有序前缀和一个无序后缀。每一轮遍历中，它从未排序部分选出最小（或最大）的元素，并将其与最左边的未排序元素交换。
After the first pass, the smallest element sits at index 0; after the second pass, the next smallest sits at index 1, and so on. The algorithm always performs exactly n–1 swaps.
第一轮遍历后，最小元素位于索引 0；第二轮后，第二小元素位于索引 1，以此类推。算法总是执行恰好 n–1 次交换。
Time complexity is O(n²) in all cases – even if the list is already sorted – because the unsorted part must be scanned for the minimum each time. This makes selection sort usually inferior to insertion sort for random data.
所有情况下的时间复杂度都是 O(n²)——即使列表已经有序——因为每次都必须扫描未排序部分以寻找最小值。这使得选择排序对随机数据通常不如插入排序。
Selection sort is not stable by default, as swapping can change the relative order of equal elements. It uses O(1) extra space. Exams often test whether you know it performs the minimum number of swaps.
选择排序默认是不稳定的，因为交换可能改变相等元素的相对顺序。它使用 O(1) 的额外空间。考试常考你是否知道它实现了最少的交换次数。
5. Merge Sort | 归并排序
Merge sort is a divide-and-conquer algorithm. It recursively splits the array into two halves until each sub-array contains a single element, then merges these sorted sub-arrays back together to produce a fully sorted array.
归并排序是一种分治算法。它递归地将数组分成两半，直到每个子数组只包含一个元素，然后把这些有序的子数组合并回一个完整的有序数组。
The merging process compares the first elements of two sorted lists and picks the smaller one, repeating until all elements are consumed. This guarantees a fully sorted output.
合并过程比较两个有序列表的第一个元素并选出较小的那个，重复这一过程直到所有元素被处理完毕。这保证了输出完全有序。
Merge sort has a time complexity of O(n log₂ n) in the best, average, and worst cases. The logarithmic depth comes from repeatedly halving, and the linear factor comes from the merging step.
归并排序在最佳、平均和最坏情况下的时间复杂度都是 O(n log₂ n)。对数深度来自反复折半，线性因子来自合并步骤。
Space complexity is O(n) because merge sort requires temporary arrays for merging. It is stable when merging does not displace equal elements from the left sub-array before those from the right.
空间复杂度为 O(n)，因为归并排序需要临时数组来进行合并。它是一种稳定的排序方法，只要在合并时不让右子数组中相等的元素先于左子数组中相等的元素。
6. Quick Sort | 快速排序
Quick sort also uses divide and conquer. It picks a pivot element and partitions the array so that all elements less than the pivot come before it, and all greater come after. The pivot is then in its final position, and the process is applied recursively to the sub-arrays.
快速排序同样采用分治策略。它选取一个枢轴元素，并对数组进行划分，使得所有小于枢轴的元素出现在它的前面，所有大于枢轴的元素出现在它的后面。此时枢轴即位于其最终位置，过程再递归应用于两个子数组。
The choice of pivot critically affects performance. A poor pivot (e.g., always the smallest or largest element) leads to O(n²) worst-case behaviour, while a good pivot yields O(n log₂ n) on average.
枢轴的选择对性能有决定性影响。糟糕的枢轴（例如始终选到最小或最大元素）会导致最坏情况的 O(n²)，而好的枢轴平均可得到 O(n log₂ n)。
Space complexity is O(log₂ n) on average due to the recursion stack. Quick sort is generally not stable because partitioning can swap elements over long distances.
平均空间复杂度为 O(log₂ n)，这是因为递归栈的深度。快速排序通常是不稳定的，因为划分过程中元素可能会被远距离交换。
Examiners often ask for a trace of the partitioning step or a comparison with merge sort regarding when to prefer which algorithm.
考官经常要求跟踪划分过程，或者比较快速排序和归并排序，说明在什么情况下应选择哪一种算法。
7. Time Complexity Comparison | 时间复杂度比较
All the quadratic sorts – bubble, insertion and selection – share O(n²) worst-case time. Insertion sort wins on small n or nearly sorted data; selection sort minimises swaps; bubble sort, even when optimised, is largely an educational tool.
所有平方阶排序——冒泡、插入和选择——最坏情况时间复杂度都是 O(n²)。插入排序在小规模或近乎有序的数据上胜出；选择排序能最小化交换次数；冒泡排序即使被优化，也主要是教学工具。
Merge sort guarantees O(n log₂ n) but needs extra memory. Quick sort is often the fastest in practice due to cache efficiency, yet it can degrade to O(n²) with unfortunate pivot choices.
归并排序可保证 O(n log₂ n)，但需要额外内存。快速排序由于缓存效率高在实践中通常最快，但如果枢轴选择不利，可能退化到 O(n²)。
The table below summarises the typical time complexities you must memorise:
下表总结了你必须记住的典型时间复杂度：
| Algorithm | Best | Average | Worst |
|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) |
| Insertion Sort | O(n) | O(n²) | O(n²) |
| Selection Sort | O(n²) | O(n²) | O(n²) |
| Merge Sort | O(n log₂ n) | O(n log₂ n) | O(n log₂ n) |
| Quick Sort | O(n log₂ n) | O(n log₂ n) | O(n²) |
Note: n is the number of elements, and log₂ denotes logarithm base 2.
注意：n 是元素个数，log₂ 表示以 2 为底的对数。
8. Stability of Sorting Algorithms | 排序算法的稳定性
A sorting algorithm is stable if it preserves the original relative order of records that have equal keys. Stability matters when sorting by multiple criteria – for example, sorting a list of students first by grade, then by name.
如果排序算法能够保持相等键值的记录原来的相对顺序，它就是稳定的。当需要按多个标准排序时，稳定性很重要——例如，先按成绩排序学生名单，再按姓名排序。
Bubble sort, insertion sort, and merge sort are naturally stable. Selection sort and the standard in-place quick sort are typically not stable. However, stable variants of quick sort exist but are rarely implemented in default libraries.
冒泡排序、插入排序和归并排序天生是稳定的。选择排序和标准原地快速排序通常是不稳定的。不过，快速排序存在稳定版本，但在默认库中很少实现。
Examination questions sometimes present a sequence of equal-valued items with subscript labels (e.g., 3ₐ, 3ₙ) to test whether you can determine if a given algorithm would reverse or preserve their order.
考试中有时会给出一组具有下标标记的等值项（例如 3ₐ, 3ₙ），以测试你是否能判断某个算法是否会颠倒或保留它们的顺序。
9. Space Complexity | 空间复杂度
In-place algorithms – bubble, insertion, selection – use a constant amount of extra memory, O(1). This makes them suitable for environments with tight memory constraints.
原地算法——冒泡、插入、选择——使用常数级的额外内存，即 O(1)。这使得它们适用于内存严格受限的环境。
Merge sort requires O(n) auxiliary space, which can be a disadvantage for large arrays. Quick sort's O(log₂ n) space stems from the recursion stack, and tail recursion can be used to minimise it, though worst case can become O(n).
归并排序需要 O(n) 的辅助空间，这对大型数组来说可能是一个缺点。快速排序的 O(log₂ n) 空间来自递归栈，可以通过尾递归来最小化它，但最坏情况可能变成 O(n)。
In written answers, always distinguish between 'auxiliary' space (extra memory beyond input) and total space. The exam may ask for space complexity with a clear definition.
在书面答题中，始终要区分 "辅助" 空间（输入之外的额外内存）和总空间。考试可能会明确要求空间复杂度，并给出清晰定义。
10. Choosing a Sorting Algorithm in Practice | 实践中排序算法的选择
For small datasets (n < 50) or almost sorted data, insertion sort is often the practical favourite due to its low overhead and O(n) best case.
对于小数据集（n < 50）或几乎有序的数据，插入排序因其低开销和 O(n) 最佳情况而经常成为实际的首选。
For large, randomly ordered datasets where stability is not required, quick sort offers excellent average performance. When stable sorting is needed and O(n log₂ n) is a must, merge sort or Timsort (a hybrid of merge and insertion) are preferred.
对于大型、随机顺序且不要求稳定性的数据集，快速排序提供了极好的平均性能。当需要稳定排序且必须保证 O(n log₂ n) 时，归并排序或 Timsort（归并和插入的混合）是首选。
Bubble and selection sorts are rarely used in production code, but they appear frequently in exams to test algorithmic thinking and complexity analysis.
冒泡和选择排序在实际生产代码中很少使用，但它们在考试中频繁出现，用以测试算法思维和复杂度分析。
11. Common Exam Pitfalls | 常见考试陷阱
Many students mistakenly assume that selection sort is stable – remember that the long-distance swap can easily reorder equal elements.
许多学生错误地认为选择排序是稳定的——请记住，远距离交换很容易重排相等的元素。
Confusing the auxiliary arrays of merge sort with quick sort's in-place partitioning is another common error. Merge sort builds new arrays; quick sort swaps within the original array.
混淆归并排序的辅助数组与快速排序的原地划分是另一个常见错误。归并排序构建新数组；快速排序在原数组内进行交换。
When asked to draw a recursion tree or illustrate the merge/partition steps, always label each level clearly and show the state of the array after each logical operation.
当被要求画出递归树或说明合并/划分步骤时，一定要清晰地标记每一层，并展示每次逻辑操作后数组的状态。
Finally, be ready to justify which sort is most appropriate for a given scenario – exam marks often depend on linking algorithm characteristics to real-world constraints like memory, dataset size, and required stability.
最后，要准备好证明哪种排序最适合特定场景——考试得分往往取决于是否能将算法特性与内存、数据集大小和所需稳定性等现实约束联系起来。
12. Summary and Key Takeaways | 总结与要点
Sorting algorithms are more than just a coding exercise; they reveal fundamental ideas about computational complexity, recursion, and in-place versus out-of-place design. Mastering the five core sorts – bubble, insertion, selection, merge, quick – gives you the toolkit to tackle both theoretical and practical problems in IB and CIE assessments.
排序算法不仅仅是编程练习；它们揭示了关于计算复杂度、递归以及原地与非原地设计的基本思想。掌握冒泡、插入、选择、归并、快速这五种核心排序，就为你提供了应对 IB 和 CIE 评估中理论和实践问题的工具包。
Remember: quadratic sorts are simple but slow; n log₂ n sorts are powerful but require care with stability and memory. Always trace with a small array to check your understanding before the final exam.
请记住：平方级排序简单但慢；n log₂ n 排序强大，但需要注意稳定性和内存。在期末考试前，始终用小数组进行跟踪以检验你的理解。
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图