📚 GCSE OCR Computer Science: Sorting Algorithms | GCSE OCR 计算机：排序算法考点精讲
Sorting algorithms are a fundamental topic in GCSE OCR Computer Science. They underpin many real-world programs and are essential for efficient data handling. In exams, you must be able to explain how core algorithms work, trace their steps on sample data, and compare their efficiency. This guide covers Bubble Sort, Insertion Sort, and Merge Sort — the three primary algorithms specified by OCR — with clear step-by-step explanations and exam-focused comparisons.
排序算法是 GCSE OCR 计算机科学的一个基础主题。它们是许多实际程序的基础，对于高效数据处理至关重要。考试中，你必须能够解释核心算法如何工作，在样本数据上跟踪其步骤，并比较它们的效率。本指南涵盖冒泡排序、插入排序和归并排序——OCR 指定的三种主要算法——提供清晰的逐步解释和面向考试的比较。
1. What Are Sorting Algorithms? | 什么是排序算法？
A sorting algorithm is a step-by-step method for arranging items in a list into a particular order, typically ascending or descending. For example, a list of numbers [5, 2, 7, 1] can be sorted to [1, 2, 5, 7]. Sorting is important because it enables faster searching (e.g., binary search requires sorted data) and makes data easier to read and analyse.
排序算法是一种将列表中的项目按特定顺序（通常是升序或降序）排列的逐步方法。例如，数字列表 [5, 2, 7, 1] 可以排序为 [1, 2, 5, 7]。排序很重要，因为它可以实现更快的搜索（例如，二分查找需要已排序的数据），并使数据更易于阅读和分析。
In computer science, we evaluate sorting algorithms based on their time complexity (how the number of comparisons grows with input size) and space complexity (extra memory used). These criteria help us choose the best algorithm for a given situation. GCSE OCR expects you to know both the mechanics of each sort and how to compare them using Big O notation.
在计算机科学中，我们基于时间复杂度（比较次数随输入规模的增长率）和空间复杂度（使用的额外内存）来评估排序算法。这些标准帮助我们为给定情况选择最佳算法。GCSE OCR 要求你了解每种排序的机制，以及如何使用大 O 表示法进行比较。
2. Bubble Sort: How It Works | 冒泡排序：工作原理
Bubble sort works by repeatedly stepping through the list, comparing each pair of adjacent elements. If a pair is in the wrong order (the left element is greater than the right in an ascending sort), the algorithm swaps them. This process is repeated for the entire list over and over until no swaps occur.
冒泡排序通过反复遍历列表，比较每一对相邻元素来工作。如果某一对顺序错误（升序排序中左边元素大于右边），算法就将它们交换。这个过程对整个列表一遍又一遍地重复，直到没有发生交换为止。
Each full traversal of the list is called a pass. After each pass, the largest unsorted element “bubbles up” to its correct position at the end of the list. Therefore, the algorithm can reduce the range of checking in the next pass, ignoring the already sorted tail. The key pseudocode is shown below.
每次完整遍历列表称为一趟（pass）。每一趟后，最大的未排序元素会“冒泡”到列表末尾的正确位置。因此，算法可以在下一趟中减少检查范围，忽略已排序的尾部。关键伪代码如下所示。
procedure bubbleSort(A : list)
n = length(A)
repeat
swapped = false
for i = 0 to n-2 do
if A[i] > A[i+1] then
swap(A[i], A[i+1])
swapped = true
end if
end for
n = n - 1
until not swapped
end procedure
Notice that the variable 'swapped' tracks whether any exchange happened. If a pass completes with no swaps, the list is already sorted and the algorithm terminates early. This early exit improves performance on partially sorted data.
请注意，变量 ‘swapped’ 跟踪是否发生了任何交换。如果一趟完成时没有发生交换，则列表已经有序，算法提前终止。这种提前退出可以改善在部分排序数据上的性能。
3. Bubble Sort Step-by-Step Example | 冒泡排序逐步示例
Let us trace bubble sort on the list [5, 3, 8, 2, 1] in ascending order. The first pass examines adjacent pairs from left to right.
让我们在列表 [5, 3, 8, 2, 1] 上跟踪冒泡排序，按升序排列。第一趟从左到右检查相邻元素对。
re 8 and 1 → swap → [3, 5, 2, 1, 8]. At the end, the largest value 8 is in final position.
第 1 趟：比较 5 和 3 → 交换（列表变为 [3, 5, 8, 2, 1]）。比较 5 和 8 → 不交换。比较 8 和 2 → 交换 → [3, 5, 2, 8, 1]。比较 8 和 1 → 交换 → [3, 5, 2, 1, 8]。结束时，最大值 8 位于最终位置。
wap → [3, 2, 5, 1, 8]. 5,1 → swap → [3, 2, 1, 5, 8]. The second largest 5 is now in place.
第 2 趟只需检查索引 0 到 3：比较 3 和 5 → 不交换。5 和 2 → 交换 → [3, 2, 5, 1, 8]。5 和 1 → 交换 → [3, 2, 1, 5, 8]。第二大的 5 现在处于正确位置。
p → [1,2]; list becomes [1,2,3,5,8]. Finally Pass 5 confirms no swaps and algorithm stops.
第 3 趟：[3,2,1] → 比较 3 和 2 交换 → [2,3,1]；3 和 1 交换 → [2,1,3]（3 正确）。第 4 趟：[2,1] → 交换 → [1,2]；列表变为 [1,2,3,5,8]。最后第 5 趟确认无交换，算法停止。
Exam tips: be ready to write down the state of the list after each pass and to identify when early termination happens. In tracing, OCR may ask you to fill in a table showing each pass.
考试提示：准备好写出每一趟后的列表状态，并识别何时发生提前终止。在跟踪题中，OCR 可能会要求你填写一个显示每一趟的表格。
4. Insertion Sort: How It Works | 插入排序：工作原理
Insertion sort builds the final sorted array one item at a time. It picks the next element from the unsorted part and inserts it into the correct position within the already sorted prefix. This is similar to how many people sort playing cards in their hands.
插入排序一次一项地构建最终有序数组。它从无序部分取出下一个元素，并将其插入到已排序前缀中的正确位置。这类似于许多人手中整理扑克牌的方式。
Initially, the first element is considered trivially sorted. Then, for each subsequent element (key), the algorithm compares it with the elements in the sorted portion moving leftwards, shifting larger elements one position to the right until the correct spot is found, and then inserts the key there.
最初，第一个元素被视为平凡有序。然后，对于每个后续元素（键值），算法将其与有序部分中的元素向左比较，将较大的元素向右移动一个位置，直到找到正确的位置，然后将键值插入该处。
procedure insertionSort(A)
for i from 1 to length(A)-1 do
key = A[i]
j = i - 1
while j >= 0 and A[j] > key do
A[j+1] = A[j]
j = j - 1
end while
A[j+1] = key
end for
end procedure
The inner loop performs shifting: it moves each element larger than the key one place right. When the loop exits, the empty cell at j+1 receives the key. This algorithm is stable and works well on small lists or partially sorted data.
内层循环执行移位操作：它将每个大于键值的元素向右移动一个位置。当循环退出时，位于 j+1 的空位接收键值。该算法是稳定的，并且在小型列表或部分排序的数据上表现良好。
5. Insertion Sort Step-by-Step Example | 插入排序逐步示例
Sort [5, 3, 8, 2, 1] using insertion sort. We start with the sorted part containing only the first element [5]. The unsorted part is [3,8,2,1].
使用插入排序对 [5, 3, 8, 2, 1] 进行排序。我们从有序部分仅包含第一个元素 [5] 开始。无序部分是 [3,8,2,1]。
list becomes [5,5,8,2,1]. Place key 3 at index 0 → [3,5,8,2,1]. Now sorted part is [3,5].
取 key = 3（索引 1）。与有序部分中的 5 比较：5 > 3，因此将 5 右移 → 列表变为 [5,5,8,2,1]。将键值 3 放入索引 0 → [3,5,8,2,1]。现在有序部分是 [3,5]。
, so no shift needed; insert 8 at its current position → [3,5,8,2,1]. Sorted part [3,5,8].
下一个键值 = 8（索引 2）。比较 8 与 5：5 < 8，因此不需要移动；将 8 插入当前位置 → [3,5,8,2,1]。有序部分 [3,5,8]。
,3: all larger → shift them right. After shifts, list becomes [3,3,5,8,1] then [5,5,8,8,1]? j=0, A[0]=3 shifted → [3,3,5,8,1]. Place key 2 at index 0 → [2,3,5,8,1]. Sorted [2,3,5,8].
键值 = 2（索引 3）。与 8,5,3 比较：全部更大 → 将它们右移。移位后，列表变为 [3,3,5,8,1] 然后 [5,5,8,8,1]？我们逐步进行：A[2]=8 移位 → [3,5,8,8,1]；j=1，A[1]=5 移位 → [3,5,5,8,1]；j=0，A[0]=3 移位 → [3,3,5,8,1]。将键值 2 放入索引 0 → [2,3,5,8,1]。有序部分 [2,3,5,8]。
8]. Sorted. When tracing in exams, you may be asked to show the list after each insertion.
最后键值 = 1。比较并移位 8,5,3,2 → 将 1 放入索引 0 → [1,2,3,5,8]。排序完成。在考试中跟踪时，可能会要求你展示每次插入后的列表。
6. Merge Sort: How It Works | 归并排序：工作原理
Merge sort is a divide-and-conquer algorithm. It splits the unsorted list into n sublists, each containing one element (which is trivially sorted). Then it repeatedly merges sublists to produce new sorted sublists until only one remains — the fully sorted list.
归并排序是一种分治算法。它将无序列表划分为 n 个子列表，每个子列表包含一个元素（该元素自然有序）。然后它反复合并子列表以生成新的有序子列表，直到只剩下一个——完全排序的列表。
The splitting phase recursively halves the list until single-element sublists are obtained. The merge phase then combines pairs of sublists by comparing the smallest unplaced elements and copying the smaller one into a temporary array, eventually producing a sorted result.
分割阶段递归地将列表对半分，直到获得单元素子列表。然后合并阶段通过比较最小未放置的元素并将较小的元素复制到临时数组中，最终生成有序结果，从而合并成对的子列表。
procedure mergeSort(A)
if length(A) <= 1 then return A
mid = length(A)/2
leftHalf = mergeSort(A[0..mid-1])
rightHalf = mergeSort(A[mid..end])
return merge(leftHalf, rightHalf)
procedure merge(left, right)
result = []
while left and right are not empty do
if left[0] <= right[0] then
append left[0] to result; remove left[0]
else
append right[0] to result; remove right[0]
end if
end while
append remaining elements of left and right to result
return result
Merge sort's recursive nature means it uses extra memory for the temporary arrays during merging. This makes its space complexity O(n), which you must consider when comparing with in-place sorts like bubble and insertion sort.
归并排序的递归特性意味着它在合并期间使用额外内存存储临时数组。这使得其空间复杂度为 O(n)，在与冒泡排序和插入排序等原地排序进行比较时必须考虑这一点。
7. Merge Sort Step-by-Step Example | 归并排序逐步示例
Let’s sort [5, 3, 8, 2, 1] with merge sort. First, split recursively: [5,3,8] and [2,1]. Split [5,3,8] into [5] and [3,8]; then [3,8] into [3] and [8]. The other half [2,1] splits to [2] and [1]. All sublists are single-element.
让我们用归并排序对 [5, 3, 8, 2, 1] 进行排序。首先，递归分割：[5,3,8] 和 [2,1]。将 [5,3,8] 分割为 [5] 和 [3,8]；然后 [3,8] 分割为 [3] 和 [8]。另一半 [2,1] 分割为 [2] 和 [1]。所有子列表都是单元素。
2] and [1] → take 1 then 2 → [1,2]. Finally merge [3,5,8] and [1,2] → compare 3 and 1 → take 1; next 3 and 2 → take 2; then rest in order → [1,2,3,5,8].
现在合并 [3] 和 [8] → 比较 3 和 8，取 3，然后 8 → [3,8]。合并 [5] 和 [3,8] → 比较 5 和 3，取 3；比较 5 和 8，取 5；然后 8 → [3,5,8]。合并 [2] 和 [1] → 取 1 然后 2 → [1,2]。最后合并 [3,5,8] 和 [1,2] → 比较 3 和 1 → 取 1；接着 3 和 2 → 取 2；然后按顺序取剩余部分 → [1,2,3,5,8]。
In OCR exam trace questions, you might be asked to show the splitting tree and the arrays produced after each merge. Practise drawing these diagrams clearly to avoid mistakes.
在 OCR 考试跟踪题中，可能会要求你展示分割树以及每次合并后产生的数组。练习清晰地绘制这些图表以避免错误。
8. Comparing Time Complexities | 时间复杂度比较
Time complexity measures how the number of comparisons grows with the number of items, n. Bubble sort and insertion sort both have worst-case and average-case time complexity O(n²). This means that if the list size doubles, the number of comparisons roughly quadruples.
时间复杂度衡量比较次数如何随项目数量 n 增长。冒泡排序和插入排序的最坏情况和平均情况时间复杂度均为 O(n²)。这意味着如果列表大小翻倍，比较次数大约翻四倍。
Merge sort, on the other hand, has a time complexity of O(n log n) in all cases. The log n factor arises from dividing the list in half repeatedly, and the n factor from the merging step that processes all elements. This gives merge sort a significant advantage for large lists.
另一方面，归并排序在所有情况下的时间复杂度均为 O(n log n)。log n 因子源于反复将列表对半分，n 因子源于处理所有元素的合并步骤。这使得归并排序对于大型列表具有显著优势。
Best-case behaviour also matters: bubble sort can achieve O(n) if the list is already sorted (due to early termination), while insertion sort also runs in O(n) on a nearly sorted list. Merge sort always does O(n log n) work, even if the list is sorted. Understanding these differences is crucial for selecting the right sort.
最佳情况行为也很重要：如果列表已经有序（由于提前终止），冒泡排序可以达到 O(n)，而插入排序在几乎有序的列表上也以 O(n) 运行。归并排序总是执行 O(n log n) 的工作，即使列表已经有序。理解这些差异对于选择正确的排序算法至关重要。
9. Stability and Space Trade-offs | 稳定性与空间权衡
A sorting algorithm is stable if it preserves the relative order of equal elements. Bubble sort and insertion sort are stable because they only swap adjacent items when strictly greater, never equal, and insertion sort inserts later equal elements after existing ones. Merge sort can be implemented to be stable by favouring the left sublist when elements are equal.
如果排序算法保持相等元素的相对顺序，则它是稳定的。冒泡排序和插入排序是稳定的，因为它们仅在严格大于时才交换相邻项，从不等于，而插入排序将后续相等元素插入到现有相等元素之后。归并排序可以通过在元素相等时优先选择左侧子列表来实现稳定。
Stability matters when sorting records by multiple keys, e.g., sorting a list of students first by grade and then by name. If the first sort is stable, the second sort does not disrupt the order within equal grades. In GCSE OCR, you may be asked to state whether an algorithm is stable.
当按多个关键字对记录进行排序时，稳定性很重要，例如，先按成绩再按姓名对学生列表进行排序。如果第一次排序是稳定的，第二次排序不会打乱相同成绩内的顺序。在 GCSE OCR 中，可能会要求你说明某个算法是否稳定。
Space complexity is the extra memory used beyond the input list. Bubble sort and insertion sort are in-place algorithms — they need only a constant amount of extra space, O(1). Merge sort requires O(n) extra space for the temporary arrays during merging. This can be a deciding factor when memory is limited.
空间复杂度是输入列表之外使用的额外内存。冒泡排序和插入排序是原地算法——它们只需要常数额外空间 O(1)。归并排序在合并期间需要 O(n) 额外空间用于临时数组。当内存有限时，这可能成为决定性因素。
10. Choosing the Right Algorithm | 选择正确的算法
For small datasets or nearly sorted data, insertion sort often outperforms the others because of its low overhead and best-case O(n) behaviour. It is also simple to implement and stable. Bubble sort is similarly simple but usually slower due to many swaps.
对于小型数据集或几乎有序的数据，插入排序通常优于其他算法，因为它开销低且具有最佳情况 O(n) 行为。它实现简单且稳定。冒泡排序同样简单，但由于大量交换通常较慢。
When sorting large datasets, merge sort's O(n log n) complexity makes it the preferred choice, despite its higher memory usage. Its predictable performance is valuable in time-critical applications. However, if memory is a major constraint, we might still consider an in‑place O(n log n) algorithm like quicksort (not in GCSE OCR) or accept slower O(n²) sorts for small n.
当排序大型数据集时，归并排序的 O(n log n) 复杂度使其成为首选，尽管其内存使用量较高。其可预测的性能在时间关键型应用中很有价值。然而，如果内存是主要限制，我们可能仍然考虑像快速排序（不在 GCSE OCR 范围内）这样的原地 O(n log n) 算法，或接受对于较小 n 的较慢 O(n²) 排序。
ight be asked to justify the choice of a sorting algorithm given a specific context, e.g., 'almost sorted small list' → insertion sort; 'large unsorted list with plenty of memory' → merge sort.
在考试情境中，可能会要求你根据特定场景证明排序算法的选择，例如，“几乎有序的小列表” → 插入排序；“内存充足的大型无序列表” → 归并排序。
11. Common Exam Pitfalls | 常见考试陷阱
Many students confuse the number of passes with the number of swaps in bubble sort. Remember that a pass is one full traversal of the list, while a swap is an exchange between two adjacent items. Questions often ask you to state the list after the first pass, not after the first swap.
许多学生混淆了冒泡排序中的趟数与交换次数。请记住，一趟是对列表的一次完整遍历，而交换是两个相邻项之间的交换。题目经常要求你给出第一趟之后的列表，而不是第一次交换之后的列表。
Another common mistake is forgetting the early termination condition. If a question states that after a certain pass no swaps occurred, bubble sort stops — do not continue performing empty passes. Similarly, in insertion sort, be careful with shifting: large elements move right, and the key is placed after all larger elements have shifted.
另一个常见错误是忘记提前终止条件。如果题目说在某一趟之后没有发生交换，冒泡排序就停止了——不要继续执行空趟。类似地，在插入排序中，小心移位：较大的元素向右移动，键值在所有较大元素移动后插入。
For merge sort, some candidates incorrectly merge before splitting completely. Always show full recursion down to single elements. Also, when merging, make sure to compare the front elements of the two sublists and deplete them correctly. Using arrows or indices in trace tables helps prevent errors.
对于归并排序，一些考生错误地在完全分割之前就进行合并。始终展示完全的递归直到单个元素。此外，合并时，确保比较两个子列表的前端元素并正确耗尽它们。在跟踪表中使用箭头或索引有助于防止错误。
12. Summary and Key Points | 总结与关键点
Bubble sort repeatedly compares adjacent items and swaps if out of order; has O(n²) average time, O(n) best, stable, in-place. Insertion sort builds the sorted list by inserting each new item; also O(n²) average, O(n) best, stable, in-place. Merge sort divides and conquers, merging sorted halves; O(n log n) for all cases, stable (if implemented carefully), requires O(n) extra memory.
冒泡排序反复比较相邻项并在顺序错误时交换；平均时间复杂度 O(n²)，最佳 O(n)，稳定，原地。插入排序通过插入每个新项构建有序列表；平均 O(n²)，最佳 O(n)，稳定，原地。归并排序分而治之，合并有序两半；所有情况 O(n log n)，稳定（若仔细实现），需要 O(n) 额外内存。
Understanding the differences in performance and memory helps you select the appropriate algorithm for a given problem. In GCSE OCR exams, you must be able to trace each algorithm on paper, compare their complexities using Big O, and discuss stability. Practise with past paper questions until you can confidently and accurately explain these sorting methods.
理解性能和内存的差异有助于你为给定问题选择合适的算法。在 GCSE OCR 考试中，你必须能够在纸上跟踪每种算法，使用大 O 比较其复杂度，并讨论稳定性。使用真题进行练习，直到你能自信且准确地解释这些排序方法。
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图