📚 Sorting Algorithm Exam Questions Decoded | 排序算法常见题型解析
Sorting algorithms are among the most frequently tested topics in computer science examinations. Whether you are preparing for A-Level, IB, or AP Computer Science, understanding how to solve sorting-related exam questions is essential for achieving top marks.
排序算法是计算机科学考试中最常考的主题之一。无论你是在准备 A-Level、IB 还是 AP 计算机科学考试，掌握排序相关题型的解题方法都是获得高分的关键。
This article provides a systematic breakdown of the most common exam question types involving sorting algorithms, including complexity analysis, stability discussions, trace tables, and code-based questions. Each section pairs an English passage with its Chinese translation to help you master both the technical content and the bilingual exam vocabulary.
本文系统梳理了排序算法最常见的考试题型，包括复杂度分析、稳定性讨论、追踪表（trace table）和代码类题目。每个章节均采用英文段落与中文段落配对的形式，帮助你同时掌握技术内容和双语考试词汇。
1. The Big-O Complexity Questions | 大 O 复杂度题型
A standard exam question asks: given an array of n elements, identify the time complexity of a specific sorting algorithm. For bubble sort, insertion sort and selection sort, the average and worst-case time complexity is O(n²). For merge sort and heap sort, the guaranteed complexity is O(n log n), whereas quick sort has an average case of O(n log n) but a worst case of O(n²) when the pivot selection is poor.
标准考题会问：给定一个包含 n 个元素的数组，指出某个排序算法的时间复杂度。冒泡排序、插入排序和选择排序的平均及最坏时间复杂度为 O(n²)。归并排序和堆排序的保证复杂度为 O(n log n)，而快速排序的平均复杂度为 O(n log n)，但在基准（pivot）选择不佳时最坏可达 O(n²)。
Examiners frequently test whether you can distinguish between the best, average, and worst-case scenarios. For an already sorted array, insertion sort and bubble sort achieve O(n) best-case performance because they only make a single pass with no swaps. This best-case behaviour never applies to selection sort, which always performs the same number of comparisons regardless of input order.
考官经常考查你是否能区分最好、平均和最坏情况。对于已排序的数组，插入排序和冒泡排序能达到 O(n) 的最好性能，因为只需一趟扫描且无需交换。选择排序永远没有这种最好情况，因为无论输入顺序如何，它总是执行相同次数的比较。
| Algorithm | Best Case | Average | Worst Case | 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) |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) |
2. Stability: Which Algorithm Preserves Order? | 稳定性：哪个算法保持原有顺序？
Stability in sorting means that two elements with equal keys retain their relative order from the original array after sorting. This property matters greatly when sorting records that are already ordered by a secondary key. Exam questions often present a list of records and ask you to identify which sorting algorithm guarantees stability.
排序中的稳定性指的是：两个关键字相等的元素在排序后仍保持它们在原数组中的相对顺序。当排序已按次关键字排列的记录时，这一性质非常重要。考题常常给出一组记录，要求你判断哪种排序算法能保证稳定性。
Bubble sort, insertion sort and merge sort are stable. Selection sort is unstable in its common in-place implementation, although it can be made stable with extra overhead. Quick sort is typically unstable because the partition step swaps distant elements across the pivot boundary. Heap sort is also unstable due to the long-distance swaps during heapify operations.
冒泡排序、插入排序和归并排序是稳定的。选择排序的常见原地实现是不稳定的，尽管通过额外开销可以使其变得稳定。快速排序通常是不稳定的，因为分区步骤会跨越基准边界交换距离较远的元素。堆排序同样不稳定，因为在堆化操作中存在远距离交换。
Stable: Bubble, Insertion, Merge
Unstable: Selection, Quick, Heap
3. Trace Table Questions | 追踪表题型
Trace table questions require you to simulate a sorting algorithm step-by-step and record the array state after each pass. The examiner may ask you to show the array after the first complete pass of bubble sort, or after each iteration of the outer loop in selection sort. Precision is essential here; one misplaced element costs you marks.
追踪表题型要求你一步步模拟排序算法，并在每趟之后记录数组的状态。考官可能要求你写出冒泡排序第一趟完整扫描后的数组，或者选择排序外层循环每一轮迭代后的数组。精确至关重要；一个元素的位置写错就会丢分。
Consider the array [64, 25, 12, 22, 11]. For selection sort, the first pass finds the minimum value 11 at index 4 and swaps it with index 0, producing [11, 25, 12, 22, 64]. The second pass finds the minimum 12 in the remaining subarray [25, 12, 22, 64] and swaps it with index 1, producing [11, 12, 25, 22, 64].
考虑数组 [64, 25, 12, 22, 11]。对于选择排序，第一趟在索引 4 处找到最小值 11，并与索引 0 交换，得到 [11, 25, 12, 22, 64]。第二趟在剩余子数组 [25, 12, 22, 64] 中找到最小值 12，与索引 1 交换，得到 [11, 12, 25, 22, 64]。
For bubble sort on the same array, the first pass compares adjacent pairs: 64 and 25 swap, 64 and 12 swap, 64 and 22 swap, 64 and 11 swap, yielding [25, 12, 22, 11, 64]. Notice that the largest element “bubbles” to the end. The second pass then operates only on the first four elements: 25 and 12 swap, 25 and 22 swap, 25 and 11 swap, yielding [12, 22, 11, 25, 64].
对同一数组进行冒泡排序，第一趟比较相邻元素：64 和 25 交换，64 和 12 交换，64 和 22 交换，64 和 11 交换，得到 [25, 12, 22, 11, 64]。注意最大元素”冒泡”到了末尾。第二趟只对前四个元素操作：25 和 12 交换，25 和 22 交换，25 和 11 交换，得到 [12, 22, 11, 25, 64]。
4. Code Completion and Logic Repair | 代码补全与逻辑修复
Many exams present a partially written sorting function and ask you to fill in the missing lines. The most common pattern is the inner-loop swap in bubble sort: if arr[j] > arr[j+1]: swap(arr[j], arr[j+1]). The direction of the comparison operator is a frequent trap: using < instead of > sorts in descending order or breaks the logic entirely.
许多考试会给出一个部分完成的排序函数，要求你补全缺失的代码行。最常见的模式是冒泡排序内层循环的交换：if arr[j] > arr[j+1]: swap(arr[j], arr[j+1])。比较运算符的方向是常见陷阱：把 < 写成 > 会导致降序排列或完全破坏逻辑。
Another common repair question involves the insertion sort inner loop. Students must identify that the code should shift elements rightward using arr[j+1] = arr[j], and that the loop condition should be while j >= 0 and arr[j] > key. Forgetting the j >= 0 boundary check is a classic off-by-one error that causes an IndexError.
另一种常见的修复题涉及插入排序的内层循环。学生必须识别出代码应使用 arr[j+1] = arr[j] 向右移动元素，且循环条件应为 while j >= 0 and arr[j] > key。忘记 j >= 0 边界检查是经典的差一错误（off-by-one），会导致 IndexError。
Insertion Sort Core Loop:
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]
j -= 1
5. Counting Comparisons and Swaps | 统计比较与交换次数
Examiners often ask you to calculate the exact number of comparisons a sorting algorithm performs on a given input. For bubble sort, the number of comparisons in the worst case equals n(n-1)/2 for an array of size n. However, if the array becomes sorted early and the code has an early-exit flag, the comparison count decreases.
考官常常要求你计算排序算法在给定输入上执行的确切比较次数。对于冒泡排序，最坏情况下比较次数等于 n(n-1)/2（数组大小为 n）。然而，如果数组提前有序并且代码带有提前退出标志，比较次数会减少。
Selection sort always performs exactly n(n-1)/2 comparisons regardless of input, because it must scan the remaining subarray completely to find the minimum each time. This makes the comparison count predictable and independent of data distribution. Swap count, however, varies from 0 to n-1 depending on input order.
选择排序无论输入如何，总是执行恰好 n(n-1)/2 次比较，因为它必须完整扫描剩余子数组才能找到最小值。这使得比较次数可预测，且与数据分布无关。但交换次数则因输入顺序不同而在 0 到 n-1 之间变化。
6. Identifying a Sort from Pseudocode | 根据伪代码识别排序算法
Exam questions frequently provide pseudocode and ask you to identify which sorting algorithm it represents. The distinguishing features are: bubble sort has adjacent swaps within nested loops and early termination; selection sort finds a minimum index in each pass; insertion sort takes one element and inserts it into the sorted section using a shifting mechanism; merge sort splits recursively and merges; quick sort selects a pivot and partitions.
考试题经常提供伪代码，要求你识别它代表哪种排序算法。区别特征包括：冒泡排序在嵌套循环中进行相邻交换并可提前终止；选择排序在每趟中找到最小索引；插入排序每次取出一个元素并通过移动机制将其插入已排序区间；归并排序递归拆分并合并；快速排序选择基准并进行分区。
When asked to identify the algorithm, also state the reason with at least two pieces of evidence. For example: “This is insertion sort because it uses a key variable extracted from the array, shifts elements using a while loop, and maintains a sorted prefix at all times.” Providing evidence-based reasoning earns partial credit even if the final identification is wrong.
当被要求识别算法时，还要给出至少两条证据来支持理由。例如：”这是插入排序，因为它从数组中取出 key 变量，使用 while 循环移动元素，并且始终保持前缀部分有序。”即使最终判断错误，基于证据的推理也能获得部分分数。
7. Memory and Space Complexity | 内存与空间复杂度
In-place algorithms such as bubble, selection, insertion, and heap sort use O(1) extra space. Merge sort requires O(n) auxiliary space because merging two sorted subarrays needs a temporary array. Quick sort requires O(log n) stack space on average for recursive calls, but degrades to O(n) in the worst case when the recursion depth equals the array size.
原地算法如冒泡、选择、插入和堆排序仅使用 O(1) 额外空间。归并排序需要 O(n) 辅助空间，因为合并两个有序子数组需要临时数组。快速排序平均需要 O(log n) 的递归栈空间，但在最坏情况下会退化到 O(n)，此时递归深度等于数组大小。
Exam questions about space complexity often require you to justify your answer. For merge sort, the key argument is that the merge step copies all n elements into a temporary buffer before writing them back. Even if you optimise the merge buffer to size n/2, the complexity class remains O(n).
关于空间复杂度的考题通常要求你说明理由。对于归并排序，核心论据是合并步骤将所有 n 个元素复制到临时缓冲区后再写回。即使你将合并缓冲区优化到 n/2 大小，复杂度级别仍然是 O(n)。
8. Worst-Case Scenario Analysis | 最坏情况分析
The most frequently tested worst-case scenario is quick sort on an already sorted array. If the pivot is always chosen as the first or last element, an already sorted array produces the worst-case partition, where one partition has size 0 and the other has size n-1. This leads to O(n²) time complexity.
最常见的考点是快速排序在已排序数组上的最坏情况。如果总是选择第一个或最后一个元素作为基准，已排序数组就会产生最坏情况分区：一个分区大小为 0，另一个为 n-1。这导致 O(n²) 的时间复杂度。
Mitigation strategies that examiners expect you to mention include: choosing a random pivot, using the median-of-three method, or using the middle element of the subarray. For heap sort, the worst case is always O(n log n) because heapify operations on any input follow a predictable structure. Knowing which data patterns trigger worst-case behaviour is a high-scoring exam skill.
考官期望你提到的缓解策略包括：随机选择基准、三数取中法（median-of-three）、或选取子数组的中间元素。对于堆排序，最坏情况始终为 O(n log n)，因为任何输入上的堆化操作都遵循可预测的结构。了解哪些数据模式会触发最坏情况是高分的应试技能。
9. Merge Sort vs Quick Sort Comparison | 归并排序与快速排序对比
Comparison-based questions that pit merge sort against quick sort are extremely common. The examiner wants you to weigh multiple factors: stability, space usage, worst-case guarantees, and practical performance. Merge sort guarantees O(n log n) and is stable, but needs O(n) extra space. Quick sort runs faster on average in practice due to better cache locality, but can degrade to O(n²) and is unstable.
将归并排序与快速排序对比的题目非常常见。考官希望你能综合考虑多个因素：稳定性、空间使用、最坏情况保证和实际性能。归并排序保证 O(n log n) 且稳定，但需要 O(n) 额外空间。快速排序由于更好的缓存局部性，平均情况下实际运行更快，但可能退化为 O(n²) 且不稳定。
When answering compare-and-contrast questions, structure your response into three distinct paragraphs: time complexity, space complexity, and stability/use cases. Mention real-world applications: merge sort is preferred for sorting linked lists because it requires no random access, while quick sort excels with arrays in memory because of its cache-friendly partition scan.
回答对比分析题时，将答案组织成三个不同段落：时间复杂度、空间复杂度和稳定性/应用场景。提及实际应用：归并排序适合链表排序因为不需要随机访问，而快速排序在内存中的数组上表现优异，因为其分区扫描对缓存友好。
10. Common Student Mistakes and Mark Schemes | 常见学生错误与评分标准
Incorrectly stating the worst-case complexity of merge sort as O(n²) is a expensive error. Another frequent mistake is confusing the number of passes with the number of comparisons. Bubble sort requires at most n-1 passes, but the total number of comparisons across all passes is about n²/2. Mark schemes award marks for each correct trace row, so never skip intermediate steps even if the final array looks correct.
把归并排序的最坏复杂度错误地写成 O(n²) 会付出惨痛代价。另一个常见错误是混淆扫描趟数和比较次数。冒泡排序最多需要 n-1 趟，但所有趟次的总比较次数约为 n²/2。评分标准对每一行正确的追踪结果都会给分，所以即使最终数组看起来正确，也绝不能跳过中间步骤。
Students also lose marks by ignoring boundary conditions in code questions, such as off-by-one errors in loop ranges, or omitting the return arr statement at the end of the function. Finally, when explaining whether an algorithm is stable, always provide a concrete example with a duplicate value to demonstrate your understanding rather than a simple yes-or-no answer.
学生在代码题中还会因为忽略边界条件而失分，比如循环范围的差一错误，或漏掉函数末尾的 return arr 语句。最后，在解释算法是否稳定时，始终用包含重复值的具体例子来展示你的理解，而不是只回答”是”或”否”。
11. Exam Strategy: Three-Step Solving Framework | 应试策略：三步解题框架
Step one is to identify the algorithm from keywords: “adjacent swap” suggests bubble sort; “minimum index” suggests selection sort; “insert into sorted region” suggests insertion sort; “recursive divide and merge” suggests merge sort. Step two is to write down the complexity table from memory of all six algorithms; this gives you a reference frame. Step three is to apply the trace or code logic systematically, one swap at a time.
第一步是从关键词识别算法：”相邻交换”提示冒泡排序；”最小索引”提示选择排序；”插入有序区域”提示插入排序；”递归分解与合并”提示归并排序。第二步是默写全部六种算法的复杂度表；这为你提供了参照框架。第三步是系统地应用追踪或代码逻辑，一次只处理一次交换。
For code questions, always test your filled-in code mentally with a small array of size 3. This catches boundary errors immediately. For trace questions, maintain a column for the original array and every intermediate step. Under exam pressure, students who write neatly structured traces are less likely to misread their own previous step and propagate an error through the entire trace.
对于代码题，始终用大小为 3 的小数组进行头脑测试。这能立即发现边界错误。对于追踪题，保留一列记录原数组和每个中间步骤。在考试压力下，书写整洁结构化追踪记录的学生不太可能读错自己前一步的结果，也避免了错误在整个追踪过程中传播。
12. Full Worked Example | 完整例题演练
Consider the exam question: “Apply quick sort to the array [33, 10, 55, 21, 47, 18], using the first element as pivot. Show the array after the first partition.” Starting with pivot = 33, use the Lomuto partition scheme with a marker at index 0. Scan from index 1: 10 is smaller, swap with marker position, marker moves to index 1; 55 is larger, skip; 21 is smaller, swap with element at marker (position 1 is 55, so it moves to index 2), marker moves to index 2; 47 is larger, skip; 18 is smaller, swap with 55 at marker index 2, marker moves to index 3. Finally swap the pivot 33 from index 0 with the element at marker index 3, which is 55. The array becomes [21, 10, 18, 33, 47, 55].
考虑这道考题：”对数组 [33, 10, 55, 21, 47, 18] 应用快速排序，使用第一个元素作为基准。写出第一次分区后的数组。”以 pivot = 33 开始，采用 Lomuto 分区方案，标记指针初始位于索引 0。从索引 1 开始扫描：10 比基准小，与标记位置交换，标记移到索引 1；55 比基准大，跳过；21 比基准小，与索引 1（即 55）交换，标记移到索引 2；47 比基准大，跳过；18 比基准小，与标记索引 2 处的 55 交换，标记移到索引 3。最后将索引 0 处的基准 33 与索引 3 处的 55 交换。数组变为 [21, 10, 18, 33, 47, 55]。
Note that 33 is now in its final sorted position. All elements to its left are smaller (21, 10, 18), and all elements to its right are larger (47, 55). In your exam answer, clearly box the final array and state that the pivot is in place, because this demonstrates that you understand the purpose of partitioning, not just the mechanical steps.
注意 33 现在处于其最终排序位置。其左边的所有元素都更小（21, 10, 18），右边的所有元素都更大（47, 55）。在考试答案中，清晰地框出最终数组，并说明基准已就位，因为这表明你理解分区的目的，而不仅仅是机械地执行步骤。
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课程辅导，国外大学本科硕士研究生博士课程论文辅导