Sorting Algorithms for IGCSE CIE Computer Science | IGCSE CIE 计算机：排序考点精讲

📚 Sorting Algorithms for IGCSE CIE Computer Science | IGCSE CIE 计算机：排序考点精讲

Understanding sorting is fundamental in computer science. For the IGCSE CIE exam (0478), you need to know how bubble sort and insertion sort work, be able to trace their steps, write or interpret pseudocode, and compare their efficiency. This article covers all essential points, from step-by-step explanations to exam tips, helping you master the sorting topic with confidence.

理解排序是计算机科学的基础。针对 IGCSE CIE 考试（0478），你需要掌握冒泡排序和插入排序的工作原理，能够跟踪它们的步骤，编写或解读伪代码，并比较它们的效率。本文涵盖从逐步解释到应试技巧的所有要点，帮助你自信地掌握排序这一考点。

1. Why Sorting Matters | 为什么排序很重要

Sorting means arranging data in a particular order, usually ascending or descending. Sorted data makes searching much faster – for example, binary search requires a sorted list to work. In real life, applications like leaderboards, contact lists and e-commerce product listings rely on sorting algorithms to display information efficiently. Understanding the logic behind sorting also strengthens your algorithmic thinking, which is a key skill examined in IGCSE Computer Science.

排序是指将数据按特定顺序排列，通常是升序或降序。有序的数据能让搜索变得快得多——例如，二分搜索需要有序的列表才能工作。在现实生活中，排行榜、联系人列表和电商产品展示等应用都依赖排序算法来高效地显示信息。理解排序背后的逻辑也能加强你的算法思维能力，这是 IGCSE 计算机科学考查的一项关键技能。

In the IGCSE syllabus, you focus on two comparison-based sorting algorithms: bubble sort and insertion sort. Neither is the fastest for huge data sets, but they are simple, clear, and excellent for learning how algorithms manipulate arrays. You must be able to describe each algorithm in words, draw its flowchart, write pseudocode, and evaluate its performance.

在 IGCSE 大纲中，你将学习两种基于比较的排序算法：冒泡排序和插入排序。这两种算法在处理海量数据时都不是最快的，但它们的逻辑简单清晰，非常适合学习算法如何操作数组。你必须能够用文字描述每种算法，绘制流程图，编写伪代码，并评估其性能。

2. Bubble Sort: Step-by-Step | 冒泡排序：逐步解析

Bubble sort works by repeatedly stepping through the list, comparing adjacent elements and swapping them if they are in the wrong order. The process is repeated until the list is sorted. During each pass, the largest unsorted element “bubbles up” to its correct position at the end of the list. If we have a list of n elements, we need at most n‑1 passes to guarantee it is sorted.

冒泡排序通过反复扫描列表，比较相邻元素并在顺序错误时交换它们来工作。这个过程会一直重复，直到列表有序为止。在每一趟扫描中，最大的未排序元素会“冒泡”到列表末端它正确的位置。如果我们有 n 个元素的列表，最多需要 n‑1 趟扫描就能保证列表有序。

Imagine sorting the list [5, 2, 9, 1, 5] in ascending order. In the first pass, we compare 5 and 2, swap them → [2, 5, 9, 1, 5]; then 5 and 9, no swap; then 9 and 1, swap → [2, 5, 1, 9, 5]; then 9 and 5, swap → [2, 5, 1, 5, 9]. After pass 1, the largest value (9) is at the end. We then repeat for the remaining unsorted part [2, 5, 1, 5], and so on. A flag can be used to detect whether any swaps occurred in a pass; if no swaps occur, the list is already sorted and the algorithm can stop early.

想象一下对列表 [5, 2, 9, 1, 5] 进行升序排序。在第一趟中，比较 5 和 2，交换 → [2, 5, 9, 1, 5]；然后 5 和 9，不交换；接着 9 和 1，交换 → [2, 5, 1, 9, 5]；最后 9 和 5，交换 → [2, 5, 1, 5, 9]。第一趟结束后，最大值 9 已在末尾。然后我们对剩下未排序的部分 [2, 5, 1, 5] 重复上述过程，以此类推。可以使用一个标志来检测某一趟是否发生了交换；如果没有交换，说明列表已经有序，算法可以提前终止。

3. Bubble Sort Pseudocode and Example | 冒泡排序伪代码与示例

Below is typical IGCSE-level pseudocode for bubble sort. It uses nested loops: the outer loop controls the number of passes, and the inner loop performs comparisons and swaps. The array index usually starts from 0.

以下是 IGCSE 级别的典型冒泡排序伪代码。它使用嵌套循环：外层循环控制扫描的趟数，内层循环执行比较和交换。数组索引通常从 0 开始。

FOR i ← 0 TO n‑2
  FOR j ← 0 TO n‑i‑2
    IF array[j] > array[j+1] THEN
      temp ← array[j]
      array[j] ← array[j+1]
      array[j+1] ← temp
    ENDIF
  NEXT j
NEXT i

Notice how the inner loop limit `n‑i‑2` ensures we do not revisit the already sorted elements at the end. After each outer loop iteration i, the largest i+1 elements are correctly placed, so the number of comparisons decreases.

注意内层循环的终止条件 `n‑i‑2`，它能确保我们不重复访问末尾已经排好的元素。每完成一次外层迭代 i，最大的 i+1 个元素都已归位，因此比较次数会逐渐减少。

Trace this pseudocode with an array of numbers, say [4, 2, 6, 3], to see how the swaps gradually sort the list. During the exam, you may be asked to complete a trace table showing the values of i, j, array and whether a swap occurs. Practice drawing such trace tables step by step.

用一个数字数组（例如 [4, 2, 6, 3]）跟踪这段伪代码，观察交换如何逐步完成排序。考试中，你可能需要补全一个追踪表，显示 i、j、数组的值以及是否发生交换。请逐步练习绘制这样的追踪表。

4. Bubble Sort Efficiency and Analysis | 冒泡排序的效率与分析

The efficiency of an algorithm measures how the time taken grows as the input size n increases. Bubble sort uses two nested loops, each roughly running n times, so the worst-case (and average) number of comparisons is about n(n‑1)/2. This gives a time complexity of O(n²) – pronounced “order of n squared”. For large lists, this quickly becomes impractical.

算法的效率衡量的是随着输入规模 n 增大，所花费时间如何增长。冒泡排序使用两个嵌套循环，每个大致运行 n 次，因此最坏情况（及平均情况）的比较次数约为 n(n‑1)/2。这给出时间复杂度 O(n²)——“n 平方的数量级”。对于大型列表，这会迅速变得不切实际。

However, bubble sort has a best-case scenario: when the list is already sorted. With the swap flag optimisation (checking if any swap happened), only one pass is needed, giving O(n) best-case time. Despite this, bubble sort is rarely used in practice for serious applications; its main value is educational, illustrating how simple algorithms can be analysed and improved.

不过，冒泡排序存在最佳情况：当列表已经有序时。借助交换标志优化（检查是否发生任何交换），只需一趟扫描即可，得到 O(n) 的最佳情况时间。尽管如此，冒泡排序在实际重要应用中很少使用；它的主要价值在于教学，展示了如何分析和改进简单的算法。

When answering exam questions about efficiency, always mention the number of passes and comparisons, the nested loop structure, and the O(n²) worst-case time. You might also be asked to compare it with insertion sort, so know both.

在回答关于效率的考试问题时，一定要提到扫描趟数和比较次数、嵌套循环结构以及 O(n²) 的最坏情况时间。你也许还需要将其与插入排序进行比较，所以要熟悉两者。

5. Insertion Sort: Step-by-Step | 插入排序：逐步解析

Insertion sort builds the final sorted array one element at a time. It picks each element from the unsorted part and inserts it into its correct position within the sorted part, shifting other elements to the right as needed. Think of how you might sort playing cards in your hand: you take one card at a time and place it in the correct order relative to the cards you already hold.

插入排序通过每次处理一个元素来构建最终的有序数组。它从无序部分取出每个元素，并将其插入到有序部分中正确的位置，根据需要将其他元素向右移动。想象一下你是如何整理手中的扑克牌：一次拿起一张牌，把它放到与手中已有牌的正确相对位置上。

Consider sorting [5, 2, 4, 6, 1]. Start with the first element (5) as the sorted part. Take the next element (2) and compare with 5; since 2 < 5, shift 5 right and insert 2 at the start → [2, 5, 4, 6, 1]. Next element 4: compare with 5 (shift 5 right), then compare with 2 (no shift), insert → [2, 4, 5, 6, 1]. Next, 6 is already larger than 5, so it stays, and finally 1 is inserted at the very beginning after shifting all others. The algorithm works efficiently on small or partially sorted data sets.

考虑对 [5, 2, 4, 6, 1] 进行排序。先将第一个元素 5 视作有序部分。取下一个元素 2，与 5 比较；因为 2 < 5，将 5 右移，把 2 插入到最前面 → [2, 5, 4, 6, 1]。下一个元素是 4：先与 5 比较（将 5 右移），再与 2 比较（不移），插入 → [2, 4, 5, 6, 1]。接着 6 已经大于 5，因此保持不动；最后，1 在移动所有其他元素后被插入到最前面。该算法在较小或部分有序的数据集上十分高效。

6. Insertion Sort Pseudocode and Example | 插入排序伪代码与示例

In IGCSE pseudocode, insertion sort typically uses a FOR loop to pick the next unsorted element (key) and a WHILE loop to shift larger elements rightwards. The key is then placed into its correct spot. The index of the first element is assumed to be 0.

在 IGCSE 伪代码中，插入排序通常使用一个 FOR 循环来选取下一个未排序元素（键），并使用一个 WHILE 循环将较大的元素向右移动。然后将键值放入正确的位置。假设第一个元素的索引为 0。

FOR i ← 1 TO n‑1
  key ← array[i]
  j ← i‑1
  WHILE j >= 0 AND array[j] > key
    array[j+1] ← array[j]
    j ← j‑1
  ENDWHILE
  array[j+1] ← key
NEXT i

Notice that the WHILE loop only runs for elements larger than the key. This means that if the list is already sorted, the inner loop never runs and the algorithm runs in O(n) time. For each iteration of the outer loop, we effectively insert one element into the sorted sublist that grows from left to right.

请注意，WHILE 循环仅对大于键值的元素执行。这意味着如果列表已经有序，内层循环根本不会运行，算法将以 O(n) 时间运行。对于外层循环的每次迭代，我们有效地将一个元素插入到从左向右增长的有序子列表中。

Let us trace insertion sort on [3, 1, 4, 2]. i=1: key=1, j=0, array[0]=3 > 1 → shift 3 right, decrement j to -1, then array[0]=1 → [1, 3, 4, 2]. i=2: key=4, j=1, array[1]=3 < 4 → no shift, array[2]=4 → [1, 3, 4, 2]. i=3: key=2, j=2 → array[2]=4 > 2 → shift 4 right; j=1 → array[1]=3 > 2 → shift 3 right; j=0 → array[0]=1 < 2 → stop, array[1]=2 → [1, 2, 3, 4].

让我们跟踪插入排序对 [3, 1, 4, 2] 的执行过程。i=1：key=1，j=0，array[0]=3 > 1 → 向右移动 3，j 减至 -1，然后 array[0]=1 → [1, 3, 4, 2]。i=2：key=4，j=1，array[1]=3 < 4 → 不移，array[2]=4 → [1, 3, 4, 2]。i=3：key=2，j=2 → array[2]=4 > 2 → 右移 4；j=1 → array[1]=3 > 2 → 右移 3；j=0 → array[0]=1 < 2 → 停止，array[1]=2 → [1, 2, 3, 4]。

7. Insertion Sort Efficiency and Analysis | 插入排序的效率与分析

Insertion sort also has a time complexity of O(n²) in the worst case (when the list is in reverse order). This is because, for each element, we may need to shift all previously sorted elements. However, its best-case performance (already sorted list) is O(n), which is better than bubble sort’s unoptimised best case. Additionally, insertion sort performs well on small or nearly sorted data, making it practical in certain real-world scenarios, like finishing a merge sort or maintaining a sorted list online.

插入排序在最坏情况（列表为逆序）下的时间复杂度也是 O(n²)。这是因为对于每个元素，我们可能需要移动所有先前已排序的元素。然而，它的最佳情况性能（已有序列表）为 O(n)，优于冒泡排序未优化时的最佳情况。此外，插入排序在小型或近乎有序的数据上表现良好，这使其在某些实际场景中很实用，比如完成归并排序的收尾工作或在线维护有序列表。

In terms of space, both bubble sort and insertion sort operate in-place – they only need a constant amount of extra memory (for variables like temp and key). This is a positive feature. In contrast to bubble sort, insertion sort usually requires fewer comparisons and swaps on average, even though they share the same big-O complexity class.

在空间方面，冒泡排序和插入排序都是原地操作——它们只需要恒定的额外内存（用于 temp 和 key 等变量）。这是一个优点。与冒泡排序相比，插入排序平均需要的比较和交换次数通常更少，尽管它们同属一个大 O 复杂度级别。

When explaining efficiency, learn to say: ‘The nested loops give approximately n²/2 comparisons, making it O(n²).’ Express the formula correctly: number of comparisons ≈ n(n‑1)/2. You may also be asked to calculate the exact number of comparisons for a given list length.

在解释效率时，要学会这样表述：“嵌套循环产生大约 n²/2 次比较，使其为 O(n²)。”正确表达公式：比较次数 ≈ n(n‑1)/2。你可能还需要针对给定的列表长度计算出确切的比较次数。

8. Comparing Bubble Sort and Insertion Sort | 比较冒泡排序与插入排序

Both algorithms are simple, stable (they preserve the relative order of equal elements), and in-place. Their worst-case and average time complexities are O(n²). However, insertion sort tends to be faster in practice because it generally makes fewer swaps. Let’s compare them side by side.

这两种算法都简单、稳定（它们保持相等元素的相对顺序）且原地操作。它们的最坏情况和平均时间复杂度均为 O(n²)。然而，插入排序在实践中往往更快，因为它通常执行更少的交换。让我们将它们进行并列比较。

Feature	Bubble Sort	Insertion Sort
Method	Repeatedly swap adjacent elements	Insert each element into sorted sublist
Best case	O(n) with swap flag	O(n)
Worst case	O(n²)	O(n²)
Swaps	Many swaps (each inversion requires one)	Shifts; typically fewer actual data movements in linked lists
Stability	Stable	Stable
Adaptivity	Can be adaptive with flag	Naturally adaptive

The exam may ask you to recommend one algorithm over the other in a given scenario. For example: ‘Which would you use for a small, almost-sorted list?’ Insertion sort is usually the better choice because it minimises unnecessary moves.

考试可能会让你在特定场景下推荐某种算法。例如：“对于一个几乎有序的小型列表，你会使用哪种算法？”插入排序通常是更好的选择，因为它能减少不必要的移动。

9. Understanding Stability and In-Place Sorting | 理解稳定性与原地排序

Stability means that two equal elements retain their original relative order after sorting. For instance, if we have two records with the same key ‘5’ and one appears before the other, a stable sort keeps them in that order. Both bubble and insertion sort are stable because they only swap or shift when one key is strictly greater than the other, not when they are equal.

稳定性意味着两个相等的元素在排序后保持其原始相对顺序。例如，如果我们有两个键值同为 ‘5’ 的记录，并且一个出现在另一个之前，稳定的排序会保持它们的这种顺序。冒泡排序和插入排序都是稳定的，因为它们仅在键值严格大于另一键值时才进行交换或移动，相等时则不会。

In-place means that the algorithm requires only a constant amount of additional memory, independent of the input size n (e.g., just one or two extra variables). Both algorithms satisfy this property, which is important for memory-constrained environments. Knowing these terms can earn you marks in definition questions.

原地操作意味着算法仅需要恒定的额外内存，与输入规模 n 无关（例如，只需一两个额外变量）。两种算法都满足这一特性，这对内存受限的环境尤为重要。理解这些术语能在定义类题目中为你赢得分数。

10. Common Exam Traps and How to Avoid Them | 常见考试陷阱与避免方法

Students often confuse the loop bounds in pseudocode. For bubble sort, remember that the outer loop runs n‑1 times, and the inner loop ends at n‑i‑2 (or equivalent). Check whether your indices start at 0 or 1 – exam papers can vary. Always read the pseudocode conventions provided in the question.

学生们经常混淆伪代码中的循环边界。对于冒泡排序，请记住外层循环运行 n‑1 次，内层循环终止于 n‑i‑2（或等价形式）。检查你的索引是从 0 还是 1 开始——考试题目可能有所不同。务必阅读题目中给出的伪代码约定。

Another pitfall is mis-tracing a pass: ensure you do not accidentally use the updated value of an element before it has been swapped. Use a trace table systematically, and verify each step. When given an array after one pass, make sure the largest (or smallest) element has bubbled to the correct end.

另一个陷阱是错误追踪一趟扫描：确保你不会在元素交换之前意外地使用更新后的值。系统地使用追踪表，并验证每一步。当给出完成一趟后的数组时，务必检查最大（或最小）元素是否已冒泡到正确的一端。

For insertion sort, the most common mistake is forgetting to shift elements before inserting the key. Always perform the right-shifting loop first, then place the key. Also, ensure you insert after decrementing j to the correct position. Practising with small arrays helps solidify these mechanics.

对于插入排序，最常见的错误是在插入键值之前忘记移动元素。始终先执行右移循环，然后放置键值。同时，确保在将 j 递减到正确位置后再进行插入。用小型数组练习有助于巩固这些机制。

11. Answering “Explain How It Works” Questions | 回答“解释其工作原理”类问题

These questions typically award marks for a clear, logical description. You can structure your answer in bullet points or numbered steps in plain English. For bubble sort, say: ‘Start at the beginning of the list. Compare the first two elements; if the first is greater than the second, swap them. Move to the next pair and repeat. After one pass, the largest element is at the end. Repeat the process for the remaining unsorted elements until no swaps occur.’

这类问题通常根据清晰、有逻辑的描述来给分。你可以用简洁的英文以要点或编号步骤的形式组织答案。对于冒泡排序，可以这样写：“从列表的开头开始。比较前两个元素；如果第一个大于第二个，交换它们。移到下一对并重复。一遍扫描后，最大元素位于末尾。对剩余未排序元素重复此过程，直到没有交换发生为止。”

For insertion sort: ‘Take the second element as the key. Compare it with the elements to its left, shifting larger elements one position to the right. Insert the key into the gap. Move to the next element and repeat until the whole list is sorted.’ Use examples to illustrate, but unless asked, you do not need to write full pseudocode in these explanation questions.

对于插入排序：“将第二个元素作为键值。将其与左边的元素进行比较，将更大的元素向右移动一个位置。将键值插入空位。移到下一个元素并重复，直到整个列表有序。”用例子进行说明，但除非有要求，在这些解释类问题中你不需要写出完整的伪代码。

12. Key Exam Tips and Final Recap | 关键考试技巧与最终回顾

To master sorting for IGCSE CIE Computer Science, practice tracing both algorithms on small arrays until you can do it without hesitation. Memorise the pseudocode patterns, and understand how loop counters relate to array indices. Be ready to analyse the number of comparisons and swaps for a specific array, not just in general terms. Pay attention to whether a question expects you to refer to bubble sort or insertion sort specifically.

要想在 IGCSE CIE 计算机科学中掌握排序，请在小数组上练习追踪两种算法，直到你能毫不犹豫地执行。记住伪代码模式，并理解循环计数器与数组索引的关系。准备好针对特定数组分析比较和交换次数，而非仅仅泛泛而谈。注意题意是要求你具体提及冒泡排序还是插入排序。

Finally, a quick checklist: can you write the bubble sort pesudocode? Can you trace insertion sort on a given list? Do you know the O(n²) and O(n) complexities, and what they mean? Can you explain why insertion sort is efficient for nearly sorted data? If yes, you are well prepared for any sorting question in the exam.

最后，快速核对清单：你能写出冒泡排序的伪代码吗？你能在给定列表上追踪插入排序吗？你知道 O(n²) 和 O(n) 复杂度的含义吗？你能解释为什么插入排序对近乎有序的数据高效吗？如果答案是肯定的，那么你就为考试中的任何排序问题做好了充分准备。

Published by TutorHao | IGCSE CIE Computer Science Revision Series | aleveler.com

更多咨询请联系16621398022（同微信）

Sorting Algorithms for IGCSE CIE Computer Science | IGCSE CIE 计算机：排序 考点精讲