📚 Sorting Algorithms in IGCSE Edexcel Computer Science | IGCSE Edexcel 计算机：排序考点精讲
Sorting is one of the most fundamental concepts in computer science. Whether you are organising contact lists, ranking exam scores, or preparing data for binary search, efficient ordering of data is essential. In the IGCSE Edexcel Computer Science specification, you are required to understand and apply three core sorting algorithms: Bubble Sort, Insertion Sort, and Merge Sort. This revision guide will walk you through each algorithm, compare their performance using Big O notation, and help you avoid common mistakes in the exam.
排序是计算机科学中最基础的概念之一。无论你是在整理通讯录、排列考试成绩，还是为二分查找准备数据，高效的数据排序都至关重要。在 IGCSE Edexcel 计算机科学考纲中，你需要理解并应用三种核心排序算法：冒泡排序、插入排序和归并排序。本考点精讲将带你逐一剖析每种算法，通过大 O 表示法比较它们的性能，并帮助你避免考试中的常见错误。
1. What is Sorting? | 什么是排序？
Sorting is the process of arranging data elements in a specific order, typically ascending or descending. Given a list of unordered items, a sorting algorithm rearranges them so that each element is either non-decreasing (for ascending) or non-increasing (for descending) in relation to the next. Sorting improves the efficiency of searching algorithms like binary search and makes data more readable for humans. In computing, sorting is applied in databases, file systems, and even in rendering graphics.
排序是将数据元素按特定顺序（通常是升序或降序）排列的过程。给定一个无序列表，排序算法会重新排列各个元素，使得相邻元素间满足非递减（升序）或非递增（降序）关系。排序能够提升二分查找等搜索算法的效率，并使数据更易于人类阅读。在计算机领域，排序被广泛应用于数据库、文件系统甚至图形渲染中。
An algorithm is a step-by-step procedure for solving a problem. Sorting algorithms can be compared based on their time complexity, space complexity, and stability. For IGCSE, you need to know how each algorithm works, how to trace it manually, and how to evaluate its efficiency using Big O notation.
算法是解决问题的分步流程。排序算法可以根据时间复杂度、空间复杂度和稳定性进行比较。在 IGCSE 考试中，你需要清楚每种算法的工作原理，能够手动追踪执行过程，并能利用大 O 表示法评估其效率。
2. Bubble Sort Algorithm | 冒泡排序算法
Bubble Sort is the simplest sorting algorithm and is often taught first. It works by repeatedly stepping through the list, comparing adjacent elements, and swapping them if they are in the wrong order. Larger elements 'bubble' to the end of the list with each pass. A complete pass without any swaps indicates the list is already sorted, allowing the algorithm to terminate early.
冒泡排序是最简单的排序算法，通常最先被讲授。它通过反复遍历列表、比较相邻元素并在顺序错误时交换它们来工作。较大的元素会像气泡一样逐渐“浮”到列表末尾。如果某次完整遍历未发生任何交换，则说明列表已有序，算法可以提前终止。
In pseudocode, the basic Bubble Sort for ascending order can be written as:
冒泡排序（升序）的伪代码可以写成：
for i = 0 to n-2
for j = 0 to n-i-2
if A[j] > A[j+1] then
swap(A[j], A[j+1])
end if
end for
end for
Here, A is an array of length n. The outer loop runs n-1 times (or fewer if an early exit condition is added). The inner loop compares adjacent pairs and shifts the largest unsorted element to its correct position at the end of the array. The variable j goes only up to n-i-2 because the last i elements are already sorted.
此处 A 是长度为 n 的数组。外层循环执行 n-1 次（若加入提前退出条件则可能更少）。内层循环比较相邻对并将当前未排序的最大元素移至数组末尾的正确位置。变量 j 仅遍历至 n-i-2，因为末尾的 i 个元素已然有序。
A manual trace helps you understand the mechanics. Consider an array [4, 2, 3, 1]. After the first full pass, the largest value 4 will be at the end. The successive passes will sort the remaining elements. You should practise tracing through each swap and recording the state of the array after every change.
手动追踪有助于理解其工作机制。考虑数组 [4, 2, 3, 1]。第一趟完整遍历后，最大值 4 会移至末尾。随后的遍历将依次排序剩余元素。你应当练习追踪每一次交换，并记录每次变化后的数组状态。
3. Insertion Sort Algorithm | 插入排序算法
Insertion Sort builds a sorted portion of the list one element at a time. It is similar to the way you might sort playing cards in your hand: you pick up a card and insert it into the correct position among the already sorted cards. Starting from the second element, the algorithm compares the current element with those in the sorted sublist to its left and shifts larger elements to the right until the correct slot is found, then inserts the element.
插入排序通过逐一构建有序片段来排序列表，其过程类似于你整理手中的扑克牌：你拿起一张牌并把它插入到已排序牌堆的正确位置。算法从第二个元素开始，将当前元素与其左侧已排序子列表中的元素进行比较，将比它大的元素向右移动，直到找到合适位置，然后插入该元素。
The pseudocode for Insertion Sort (ascending) is:
插入排序（升序）的伪代码为：
for i = 1 to n-1
current = A[i]
j = i - 1
while j >= 0 and A[j] > current
A[j+1] = A[j]
j = j - 1
end while
A[j+1] = current
end for
In this pseudocode, current stores the value to be inserted. The inner while loop shifts elements greater than current one position to the right. Once the correct position is found (either when a smaller element is met or the beginning of the array is reached), the current value is placed. This algorithm is stable and works efficiently on nearly sorted data.
在这段伪代码中，current 存储将要插入的值。内层 while 循环将大于 current 的元素依次右移一位。一旦找到正确位置（遇到更小元素或到达数组开头），即将 current 放入该处。该算法是稳定的，对近乎有序的数据效率极高。
For example, sorting [3, 1, 4, 2] with Insertion Sort: start with element at index 1 (value 1), compare with 3, shift 3 to the right, then place 1 at index 0. The array becomes [1, 3, 4, 2]. Next, value 4 is already in place relative to its left. Then value 2 is compared with 4 and 3, shifting them right, and inserted after 1, resulting in [1, 2, 3, 4].
例如，使用插入排序对 [3, 1, 4, 2] 进行排序：从索引 1 的元素（值 1）开始，与 3 比较，将 3 右移，然后将 1 放置在索引 0 处。数组变为 [1, 3, 4, 2]。接着，值 4 相对于左侧已有序。然后值 2 与 4 和 3 比较，将它们右移，最后插入到 1 之后，得到 [1, 2, 3, 4]。
4. Merge Sort Algorithm | 归并排序算法
Merge Sort is a divide-and-conquer algorithm that recursively splits the list into smaller sublists until each sublist contains only one element (which is trivially sorted). Then, it repeatedly merges these sublists back together in sorted order to produce a fully sorted list. This algorithm is far more efficient on large datasets than Bubble Sort or Insertion Sort.
归并排序是一种分治算法，它递归地将列表拆分成更小的子列表，直至每个子列表仅含一个元素（此时自然有序）。然后，它不断将这些子列表按序合并，最终生成完整的有序列表。该算法在处理大数据集时比冒泡排序和插入排序高效得多。
A high-level description of Merge Sort:
归并排序的高层描述：
- Divide the unsorted list into two halves recursively until each sublist has length 1.
- 将未排序列表递归地分成两半，直至子列表长度为 1。
- Merge pairs of sublists by comparing the smallest elements of each and taking the smaller one, building up sorted sublists.
- 通过比较各子列表的最小元素并取出较小的那个，成对合并子列表，构建有序子列表。
- Repeat merging until a single sorted list remains.
- 重复合并过程，直至剩下一个有序列表。
The merging step is crucial. For example, merging two sorted lists [2, 4] and [1, 5]: you compare 2 with 1, take 1; compare 2 with 5, take 2; then take 4 and then 5. The result is [1, 2, 4, 5]. This is repeated at each level of recursion.
合并步骤至关重要。例如，合并两个有序列表 [2, 4] 和 [1, 5]：比较 2 与 1，取出 1；比较 2 与 5，取出 2；然后依次取出 4 和 5。结果为 [1, 2, 4, 5]。这一过程在递归的每一层重复执行。
Merge Sort's time complexity is O(n log₂ n) in all cases, making it very predictable. However, it requires additional memory for the temporary sublists, which yields a space complexity of O(n). You may be asked to trace a merge step or draw a tree diagram showing how the list splits and merges.
归并排序在任何情况下的时间复杂度均为 O(n log₂ n)，具有极高的可预测性。但它需要额外的内存来存储临时子列表，因此空间复杂度为 O(n)。考试中可能要求你追踪某一合并步骤，或画出展示列表拆分与合并的树状图。
5. Comparing Sorting Algorithms | 排序算法对比
When evaluating sorting algorithms, we consider time complexity (best, average, and worst cases), space complexity, and stability. Stability means that equal elements retain their relative order after sorting. Understanding these differences helps you choose the right algorithm for a given situation.
在评估排序算法时，我们会考虑时间复杂度（最好、平均和最坏情况）、空间复杂度以及稳定性。稳定性即相等元素在排序后仍保持原有的相对顺序。理解这些差异有助于你为特定场景选择合适的算法。
The table below summarises the three IGCSE sorting algorithms:
下表总结了三种 IGCSE 排序算法：
| Algorithm (算法) | Best Case (最好情况) | Average Case (平均情况) | Worst Case (最坏情况) | Space (空间) | Stable? (稳定?) |
|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Yes (是) |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Yes (是) |
| Merge Sort | O(n log₂ n) | O(n log₂ n) | O(n log₂ n) | O(n) | Yes (是) |
Bubble Sort and Insertion Sort are O(n²) in the average and worst cases, meaning their running time grows quadratically with the input size. However, both can achieve O(n) in the best case: Bubble Sort when no swaps are needed (already sorted), and Insertion Sort when the list is nearly sorted. Merge Sort consistently runs in O(n log₂ n) time but uses extra memory.
冒泡排序和插入排序在平均和最坏情况下为 O(n²)，这意味着它们的运行时间随输入规模呈平方增长。但在最好情况下，两者均可达到 O(n)：冒泡排序在无需交换（已有序）时，插入排序在列表近乎有序时。归并排序始终保持 O(n log₂ n) 的时间性能，但需要额外内存。
6. Understanding Big O Notation | 理解大O表示法
Big O notation describes how the number of operations required by an algorithm grows as the size of the input (n) increases. It focuses on the dominant term and ignores constant factors. For sorting, we primarily look at comparisons and swaps. An algorithm with O(n²) might be fine for small n but becomes impractical for thousands of items.
大O表示法描述了算法所需的操作次数如何随输入规模（n）增长。它着眼于主导项而忽略常数因子。在排序中，我们主要关注比较和交换的次数。O(n²) 的算法对较小规模 n 或许可行，但在处理数千个数据时则不堪使用。
For exam purposes, you should be comfortable interpreting O(n), O(n²), O(n log₂ n), and O(1). O(1) means constant space or time, independent of n. Tracing the number of operations for a small example can help you deduce the complexity class. You may also be asked to identify the worst-case scenario for a given algorithm – for example, a reverse-sorted list for Bubble Sort.
就考试而言，你需要熟练解读 O(n)、O(n²)、O(n log₂ n) 和 O(1)。O(1) 表示与 n 无关的常数级空间或时间。通过追踪小规模示例中的操作次数，可以推断出其复杂度类别。你可能还会被要求识别某一算法的最坏情况——例如，冒泡排序的最坏情况是逆序列表。
Remember that Big O gives an upper bound on growth, so it tells you how bad things can get when n is large. It does not tell you which algorithm is faster for a specific small dataset – that is where constant factors and practical implementation details matter.
请记住，大O给出的是增长的上界，因此它告诉你当 n 很大时情况会变得多糟，但它并不说明哪个算法在特定小数据集上更快——此时常数因子和实际实现细节就会发挥作用。
7. Tracing Sorting Algorithms Step by Step | 逐步追踪排序算法
IGCSE exam questions often ask you to complete a trace table or write out the intermediate states of an array after each pass or comparison. You must show each swap or shift clearly. For Bubble Sort, you would list the array after each inner loop or after each swap. For Insertion Sort, you might show the sorted sublist expand. For Merge Sort, you could draw a tree to show splitting and merging steps.
IGCSE 考题常要求你完成追踪表格，或写出每次遍历、每次比较后数组的中间状态。你必须清晰地展示每一次交换或移位。对于冒泡排序，你需要列出每次内循环后或每次交换后的数组。对于插入排序，你可能需要展示有序子列表的扩展。对于归并排序，你可以画出树形图来表现拆分和合并的步骤。
A trace table for Bubble Sort on [3, 2, 5, 1] might have columns for i, j, A[j], A[j+1], Swap?, and the array after swap. Practise completing such tables under timed conditions. Precision matters: if you miss one swap, the entire trace can become incorrect, losing marks.
对 [3, 2, 5, 1] 执行冒泡排序的追踪表可能包含 i、j、A[j]、A[j+1]、是否交换以及交换后的数组等列。请在限时条件下练习完成这类表格。准确性至关重要：漏掉一次交换就可能导致整个追踪错误，从而失分。
When tracing Merge Sort, label the levels of recursion. For instance, splitting [38, 27, 43, 3] into [38, 27] and [43, 3], then further splitting until single elements, then merging stepwise. Exam answers often require you to show the merged sublist at each stage visually.
追踪归并排序时，请标注递归层级。例如，将 [38, 27, 43, 3] 拆分为 [38, 27] 和 [43, 3]，再进一步拆分至单个元素，最后逐步合并。考试答案通常要求你直观地展示每一阶段合并后的子列表。
8. Common Exam Mistakes and Tips | 常见考试错误与技巧
Many students lose marks by confusing the inner and outer loops of Bubble Sort. Remember that the outer loop controls the number of passes, and the inner loop handles comparisons. Setting the correct bounds for j is vital. Another pitfall is forgetting to stop the inner loop early in Bubble Sort after each pass: the last i elements are already sorted, so j must end at n-i-2.
许多学生因混淆冒泡排序的内外层循环而失分。请记住，外层循环控制遍历的趟数，内层循环处理相邻比较。正确设定 j 的终止界限至关重要。另一个易错点是忘记在每趟遍历后提前终止内循环：末尾的 i 个元素已经有序，因此 j 必须终止于 n-i-2。
fore shifting. If you overwrite it, you lose the data. Always store the current element as 'key' or 'current' e and use the while loop to shift, then insert. Also, watch the condition of the while loop: j must be >= 0.
对于插入排序，常见错误是在移位前未能将要插入的值保存在临时变量中。一旦覆盖，数据便会丢失。务必以 'key' 或 'current' 存储当前元素，并使用 while 循环进行移位，然后再插入。同时要注意 while 循环的条件：j 必须 >= 0。
When discussing Merge Sort, do not confuse it with Quick Sort. Merge Sort always splits the list from the middle; it does not choose a pivot. Be clear about the merging process: you compare the front elements of the two sublists and take the smaller one. The algorithm uses extra arrays, so watch your space complexity statements.
讨论归并排序时，切勿与快速排序混淆。归并排序总是从中间拆分列表，而不选择枢轴。请明确合并过程：比较两个子列表的前端元素并取出较小的那个。该算法使用额外数组，因此要注意空间复杂度的表述。
A final tip: in written questions, use precise terminology such as 'pass', 'swap', 'shift', 'divide', 'conquer', and 'merge'. Bullet-point answers are acceptable, but ensure you fully explain the steps. Practise past paper questions and self-trace algorithms with different types of input, including already sorted, reverse sorted, and random data.
最后一点建议：在文字题中，请使用精确术语，如“遍历”（pass）、“交换”（swap）、“移位”（shift）、“分”（divide）、“治”（conquer）、“合并”（merge）。分点作答是可以接受的，但务必充分解释每个步骤。练习历年真题，并用不同类型的输入（包含已有序、逆序和随机数据）自行追踪算法。
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图