Sorting Algorithms Explained | 排序算法考点精讲

📚 Sorting Algorithms Explained | 排序算法考点精讲

Welcome to your focused revision guide on sorting algorithms for the IGCSE AQA Computer Science specification. Sorting is the process of arranging data in a particular order, most commonly numerical or alphabetical. Understanding how different sorting methods work, their efficiency, and when to apply them is a core skill for this syllabus. In this article, we will walk through the key algorithms you need to know, compare their performance, and solidify your grasp of computational thinking with clear, bilingual explanations.

欢迎来到专为 IGCSE AQA 计算机科学大纲设计的排序算法复习指南。排序是将数据按特定顺序（最常见的是数值或字母顺序）排列的过程。理解不同排序方法如何运作、它们的效率以及何时应用它们，是这门课程的核心技能。在本文中，我们将逐一讲解你需要掌握的关键算法，比较它们的性能，并通过清晰的双语解释巩固你对计算思维的理解。

1. What is Sorting? | 什么是排序？

Sorting is a fundamental operation in computer science that organises a list of items into a defined order. The order can be ascending (smallest to largest, A to Z) or descending (largest to smallest, Z to A). Sorting makes data easier to search, analyse, and visualise. Almost every computer system relies on sorted data in some form, from search engines to e-commerce product listings.

排序是计算机科学中的一项基本操作，它将一系列项目组织成定义好的顺序。顺序可以是升序（从小到大，A 到 Z）或降序（从大到小，Z 到 A）。排序使数据更易于搜索、分析和可视化。几乎每个计算机系统都以某种形式依赖排序后的数据，从搜索引擎到电子商务产品列表。

In your IGCSE exam, you will be expected to trace, explain, and compare sorting algorithms. You should also be able to identify situations where a particular algorithm is suitable. The main sorting algorithms covered are bubble sort, insertion sort, and merge sort. Each has unique characteristics and performance trade-offs.

在 IGCSE 考试中，你需要能够追踪、解释和比较排序算法。你还应能识别特定算法适合的情况。涵盖的主要排序算法有冒泡排序、插入排序和归并排序。每种算法都有独特的特性和性能权衡。

2. Bubble Sort – The Simplest Algorithm | 冒泡排序——最简单的算法

Bubble sort works by repeatedly stepping through the list, comparing adjacent elements and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. It is called “bubble” sort because smaller elements “bubble” to the beginning of the list (or larger ones sink to the end) like bubbles in water.

冒泡排序通过反复遍历列表来工作，比较相邻的元素，如果它们的顺序错误就交换它们。对列表的遍历会一直重复，直到不再需要交换，这表明列表已排序。它被称为“冒泡”排序，是因为较小的元素会像水中的气泡一样“浮”到列表的开头（或者较大的元素沉到底部）。

Let’s trace an example with the list [5, 1, 4, 2, 8] in ascending order:

让我们用一个升序列表 [5, 1, 4, 2, 8] 来追踪一个例子：

First pass: compare 5 and 1 → swap → [1, 5, 4, 2, 8]; compare 5 and 4 → swap → [1, 4, 5, 2, 8]; compare 5 and 2 → swap → [1, 4, 2, 5, 8]; compare 5 and 8 → no swap. End of pass 1.
第一趟：比较 5 和 1 → 交换 → [1, 5, 4, 2, 8]；比较 5 和 4 → 交换 → [1, 4, 5, 2, 8]；比较 5 和 2 → 交换 → [1, 4, 2, 5, 8]；比较 5 和 8 → 不交换。第一趟结束。
Second pass: [1, 4, 2, 5, 8] → compare 1 and 4 (no swap), 4 and 2 → swap → [1, 2, 4, 5, 8]; rest no swaps.
第二趟：[1, 4, 2, 5, 8] → 比较 1 和 4（不交换），4 和 2 → 交换 → [1, 2, 4, 5, 8]；其余不交换。
Third pass checks and finds no swaps needed, so the list is sorted.
第三趟检查发现不需要交换，因此列表已排序。

Bubble sort is easy to understand but very inefficient on large lists. Its worst-case and average time complexity is O(n²), where n is the number of items. A key feature of bubble sort is that after each complete pass, the largest unsorted element is guaranteed to be in its final position.

冒泡排序易于理解，但在大型列表中效率非常低。它的最坏情况和平均时间复杂度是 O(n²)，其中 n 是项的数量。冒泡排序的一个关键特征是，在每次完整遍历之后，最大的未排序元素一定会处于其最终位置。

3. Insertion Sort – Building a Sorted List | 插入排序——构建有序列表

Insertion sort builds the final sorted array one item at a time. It works by taking each element from the unsorted part and inserting it into its correct position within the sorted part of the list. It is much like the way you might sort playing cards in your hand: you pick a card and place it in the correct order among the cards you already hold.

插入排序一次一个元素地构建最终的有序数组。它从未排序部分取出每个元素，并将其插入到列表已排序部分中的正确位置。这很像你手中整理扑克牌的方式：你拿起一张牌，把它插到你已经拿着的牌中正确的位置。

Consider the list [9, 5, 1, 4, 3] sorted in ascending order:

考虑列表 [9, 5, 1, 4, 3] 按升序排序：

Start with the first element (9) considered sorted.
从第一个元素 (9) 开始视为已排序。
Take 5: compare with 9, shift 9 right, insert 5 → [5, 9, 1, 4, 3]
取 5：与 9 比较，将 9 右移，插入 5 → [5, 9, 1, 4, 3]
Take 1: compare with 9 (shift), compare with 5 (shift), insert 1 → [1, 5, 9, 4, 3]
取 1：与 9 比较（移位），与 5 比较（移位），插入 1 → [1, 5, 9, 4, 3]
Take 4: compare with 9 (shift), 5 (shift), insert 4 → [1, 4, 5, 9, 3]
取 4：与 9 比较（移位），5（移位），插入 4 → [1, 4, 5, 9, 3]
Take 3: compare and shift 9, 5, 4, insert 3 → [1, 3, 4, 5, 9]
取 3：比较并移位 9, 5, 4，插入 3 → [1, 3, 4, 5, 9]

Insertion sort has a worst-case and average time complexity of O(n²) as well. However, it performs much better than bubble sort in practice for small or nearly sorted lists. Its best-case time complexity is O(n) when the list is already sorted. It is a stable sorting algorithm, meaning that equal elements retain their relative order.

插入排序的最坏情况和平均时间复杂度也是 O(n²)。然而，在实践中，对于小型或几乎有序的列表，它的性能比冒泡排序好得多。当列表已经排序时，它的最佳情况时间复杂度是 O(n)。它是一种稳定的排序算法，意味着相等元素保持它们的相对顺序。

4. Merge Sort – Divide and Conquer | 归并排序——分而治之

Merge sort is a much more efficient algorithm that uses the divide-and-conquer strategy. It recursively splits the list into smaller sublists until each sublist contains only one element (which is trivially sorted). Then it repeatedly merges the sublists back together, comparing elements and building a new sorted list at each merge step.

归并排序是一种效率高得多的算法，采用分治策略。它递归地将列表分割成更小的子列表，直到每个子列表只包含一个元素（这显然是已排序的）。然后它反复将子列表合并回来，在每一步合并时比较元素并构建新的有序列表。

Let’s trace merge sort on [38, 27, 43, 3, 9, 82, 10]:

我们来追踪归并排序对 [38, 27, 43, 3, 9, 82, 10] 的操作：

Split: [38, 27, 43, 3] and [9, 82, 10]; continue splitting until single elements.
分割：[38, 27, 43, 3] 和 [9, 82, 10]；继续分割直到单个元素。
Left half: [38, 27] → [38] and [27]; merge → [27, 38]
左半部分：[38, 27] → [38] 和 [27]；合并 → [27, 38]
[43, 3] → [43] and [3]; merge → [3, 43]
[43, 3] → [43] 和 [3]；合并 → [3, 43]
Merge [27, 38] and [3, 43] → compare 27 and 3 → 3, then 27, then 38, then 43 → [3, 27, 38, 43]
合并 [27, 38] 和 [3, 43] → 比较 27 和 3 → 3，然后 27，然后 38，然后 43 → [3, 27, 38, 43]
Right half similarly becomes [9, 10, 82]
右半部分类似地变成 [9, 10, 82]
Final merge: [3, 27, 38, 43] and [9, 10, 82] → [3, 9, 10, 27, 38, 43, 82]
最终合并：[3, 27, 38, 43] 和 [9, 10, 82] → [3, 9, 10, 27, 38, 43, 82]

Merge sort has a worst-case time complexity of O(n log n), making it significantly faster for large datasets compared to O(n²) algorithms. However, it requires additional memory space proportional to the list size to hold the temporary arrays during merging. This is an example of a trade-off between time and space.

归并排序的最坏情况时间复杂度为 O(n log n)，这使得它在处理大数据集时比 O(n²) 算法快得多。然而，它需要与列表大小成比例的额外内存空间来在合并期间存放临时数组。这是时间与空间之间权衡的一个例子。

5. Comparing Complexity – O(n²) vs O(n log n) | 复杂度比较——O(n²) 对比 O(n log n)

Time complexity describes how the execution time of an algorithm grows with the size of the input. For sorting algorithms, the most important complexities are O(n²) for bubble and insertion sort (average/worst), and O(n log n) for merge sort. In Big O notation, we ignore constants and lower-order terms because they become negligible for large n.

时间复杂度描述了算法的执行时间如何随着输入规模的增长而增长。对于排序算法，最重要的复杂度是冒泡和插入排序的 O(n²)（平均/最坏情况），以及归并排序的 O(n log n)。在大 O 表示法中，我们忽略常数和低阶项，因为当 n 很大时它们可以忽略不计。

To illustrate the difference, consider sorting 1,000 items:

为了说明差异，考虑对 1000 个项目进行排序：

O(n²) algorithm: roughly 1,000,000 comparison operations.
O(n²) 算法：大约 1,000,000 次比较操作。
O(n log n) algorithm: roughly 1000 × 10 = 10,000 comparisons (using log base 2).
O(n log n) 算法：大约 1000 × 10 = 10,000 次比较（使用以 2 为底的对数）。

As n grows, the gap becomes enormous. For 1,000,000 items, O(n²) would take around 10¹² operations, while O(n log n) would take about 20 million. This explains why merge sort is preferred for large datasets.

随着 n 的增长，差距变得巨大。对于 1,000,000 个项目，O(n²) 将需要大约 10¹² 次操作，而 O(n log n) 大约需要 2000 万次。这解释了为什么对于大数据集归并排序是更优选择。

Space complexity also matters: bubble and insertion sort work in-place (O(1) extra space), while merge sort requires O(n) extra space. In memory-constrained environments, an in-place algorithm may be preferable.

空间复杂度也很重要：冒泡和插入排序是原地工作（O(1) 额外空间），而归并排序需要 O(n) 额外空间。在内存受限的环境中，原地算法可能更可取。

6. Tracing Algorithms Step by Step | 逐步追踪算法

In your IGCSE exam, you may be asked to complete a trace table for a sorting algorithm or show the state of a list after each pass. You must be systematic and careful to record each comparison and swap.

在你的 IGCSE 考试中，你可能会被要求完成一个排序算法的追踪表格，或显示每次遍历后列表的状态。你必须系统化且仔细地记录每次比较和交换。

For bubble sort tracing, remember to show the list at the start of each pass and after each swap. A typical trace table might have columns for pass number, current pair being compared, action (swap/no swap), and the resulting list.

对于冒泡排序的追踪，记住在每次遍历开始时和每次交换后显示列表。一个典型的追踪表格可能包含列：遍历次数、当前正在比较的一对、操作（交换/不交换）以及结果列表。

For merge sort, you often need to show the splitting tree and the merging steps. Be clear about which sublists are being merged at each stage. Practice with small lists to ensure you never make a mistake in ordering.

对于归并排序，你通常需要展示分割树和合并步骤。要清楚地说明在每个阶段正在合并哪些子列表。用小列表进行练习，以确保你不会在排序上犯错。

Insertion sort tracing often involves showing a horizontal line separating the sorted part from the unsorted part, and showing how the next element is inserted by shifting larger elements to the right.

插入排序的追踪通常涉及展示一条水平线，将已排序部分与未排序部分分开，并展示如何通过将较大的元素向右移位来插入下一个元素。

7. Key Characteristics: Stability, Adaptivity, and In-place | 关键特性：稳定性、自适应性和原地性

Sorting algorithms have properties that help programmers choose between them. A sorting algorithm is stable if it preserves the relative order of items with equal keys. This is crucial when sorting by multiple criteria; for example, sorting a list of students by grade and then by name should keep students with the same grade in alphabetical order if the second sort is stable.

排序算法具有一些特性，可帮助程序员在它们之间进行选择。如果算法能保持具有相等键值的项的相对顺序，那么它就是稳定的。这在按多个条件排序时至关重要；例如，先按成绩然后按姓名对学生列表排序，如果第二次排序是稳定的，那么成绩相同的学生将保持字母顺序。

Bubble sort and insertion sort are stable. Merge sort can be implemented as stable. The property of adaptivity means an algorithm takes advantage of existing order in the input to perform faster. Insertion sort is adaptive: it performs well on nearly sorted data (O(n) best case). Bubble sort can be made adaptive with a flag to detect when no swaps occurred.

冒泡排序和插入排序是稳定的。归并排序可以被实现为稳定的。自适应性是指算法利用输入中已有的顺序来更快地执行。插入排序是自适应的：它在几乎有序的数据上表现很好（最佳情况 O(n)）。冒泡排序可以通过一个标志来检测是否没有发生交换，从而变得自适应。

An in-place algorithm uses only a constant amount of extra memory (O(1) space). Bubble and insertion sort are in-place; merge sort is not because it requires auxiliary arrays. This distinction becomes important on memory-constrained devices.

原地算法只使用常量级的额外内存（O(1) 空间）。冒泡和插入排序是原地的；归并排序不是，因为它需要辅助数组。这一区别在内存受限的设备上变得很重要。

8. Pseudocode for Bubble Sort | 冒泡排序的伪代码

You should be comfortable reading and writing simple pseudocode for the sorting algorithms. Here is a typical representation of bubble sort:

你应该能够轻松地阅读和编写这些排序算法的简单伪代码。以下是冒泡排序的一个典型表示：

FOR i ← 0 TO n-2
   FOR j ← 0 TO n-i-2
     IF arr[j] > arr[j+1] THEN
       SWAP arr[j] AND arr[j+1]
     ENDIF
   ENDFOR
ENDFOR

The outer loop controls the number of passes. Notice how the inner loop’s range decreases after each pass because the largest elements are already placed at the end. In an optimised version, we can add a boolean variable to break early if the list becomes sorted before all passes complete.

外层循环控制遍历的次数。注意内层循环的范围在每次遍历后都会减少，因为最大的元素已经被放置在末尾。在优化版本中，我们可以添加一个布尔变量，如果列表在所有遍次完成之前已经有序，就可以提前退出。

Be able to translate such pseudocode into a trace table and vice versa. Understanding the indexes and loop bounds is crucial for the exam.

要能够将这样的伪代码转换为追踪表格，反之亦然。理解索引和循环边界对考试至关重要。

9. Pseudocode for Insertion Sort | 插入排序的伪代码

Insertion sort pseudocode often looks like this:

插入排序的伪代码通常如下所示：

FOR i ← 1 TO n-1
   key ← arr[i]
   j ← i – 1
   WHILE j >= 0 AND arr[j] > key
     arr[j+1] ← arr[j]
     j ← j – 1
   ENDWHILE
   arr[j+1] ← key
ENDFOR

The algorithm picks the element at index i as the key, and shifts all elements greater than key one position to the right. Once the correct position is found, the key is inserted. Note that it starts from i=1 because the first element is considered trivially sorted.

该算法选索引 i 处的元素作为 key，并将所有大于 key 的元素向右移动一个位置。一旦找到正确的位置，就将 key 插入。注意它从 i=1 开始，因为第一个元素被视为显然是已排序的。

Practising this pseudocode with a trace will reinforce your understanding. Make sure you can identify the best and worst cases based on the number of shifts.

通过追踪练习这些伪代码将巩固你的理解。确保你能根据移位的次数识别最佳和最坏情况。

10. Pseudocode for Merge Sort | 归并排序的伪代码

Merge sort is more complex because it involves recursion. A typical high-level pseudocode is:

归并排序更复杂，因为它涉及递归。一个典型的高层伪代码如下：

PROCEDURE mergeSort(arr, left, right)
   IF left < right THEN
     mid ← (left + right) / 2
     mergeSort(arr, left, mid)
     mergeSort(arr, mid+1, right)
     merge(arr, left, mid, right)
   ENDIF
ENDPROCEDURE

The merge procedure itself creates temporary arrays for the left and right halves, then compares elements one by one to build the sorted combined list. You should understand the recursive splitting and the merging logic, although you may not be asked to write the full merge pseudo code from scratch in IGCSE. Being able to interpret it and trace an example is essential.

merge 过程本身会为左右两半创建临时数组，然后逐个比较元素以构建有序的组合列表。你应该理解递归分割和合并的逻辑，尽管在 IGCSE 中你可能不会被要求从零开始写出完整的 merge 伪代码。能够解释它并追踪一个例子是至关重要的。

11. Choosing the Right Sort – Exam Scenarios | 选择合适的排序——考试场景

Exam questions often ask you to recommend a sorting algorithm for a given situation. For example:

考试问题经常要求你为给定的情况推荐一种排序算法。例如：

Small list (n < 50): Insertion sort is often a good choice because of its simplicity and low overhead. Bubble sort is acceptable but less efficient.
小列表 (n < 50)：插入排序通常是一个不错的选择，因为它简单且开销低。冒泡排序可以接受但效率较低。
Nearly sorted data: Insertion sort excels here, running close to O(n) time. Bubble sort with early exit can also be used.
几乎有序的数据：插入排序在这里表现出色，运行时间接近 O(n)。带有提前退出的冒泡排序也可以使用。
Large dataset (n > 1000): Merge sort is preferred due to its O(n log n) time complexity, avoiding the quadratic slowdown of simpler sorts.
大数据集 (n > 1000)：归并排序由于 O(n log n) 的时间复杂度而更受青睐，避免了简单排序的二次方级减速。
Stability required: Choose bubble, insertion, or a stable merge sort.
要求稳定性：选择冒泡、插入或稳定的归并排序。
Memory constraints: Avoid merge sort; use in-place algorithms like insertion sort or bubble sort.
内存受限：避免归并排序；使用原地算法，如插入排序或冒泡排序。

You should be able to justify your choice by referring to time and space complexity, as well as algorithm properties. Practise such recommendation questions with short paragraphs linking the scenario properties to the algorithm features.

你应该能够通过提及时间和空间复杂度以及算法特性来证明你的选择。练习此类推荐题，用简短的段落将场景特性与算法特性联系起来。

12. Common Mistakes and How to Avoid Them | 常见错误及如何避免

Students often lose marks by confusing the direction of sorting or forgetting that bubble sort’s inner loop shrinks. Always double-check whether the question requires ascending or descending order. In tracing, one common error is forgetting to stop bubble sort early when a pass has no swaps; always check for the early termination condition if you are implementing an optimised version.

学生常常因混淆排序方向或忘记冒泡排序内循环会缩小而丢分。始终仔细检查问题是要求升序还是降序。在追踪中，一个常见错误是当某一趟没有交换时忘记提前停止冒泡排序；如果你在实现优化版本，一定要检查提前终止条件。

In insertion sort, students sometimes start the key element from the wrong index or fail to shift elements correctly. Remember the sorted portion grows from the left. In merge sort, a typical mistake is incorrectly merging the sublists, especially when one sublist is exhausted before the other. Always compare the current elements of both sublists and append the smaller one, then copy any remaining elements.

在插入排序中，学生有时会从错误的索引开始 key 元素，或未能正确移动元素。记住已排序部分是从左侧增长的。在归并排序中，一个典型错误是错误地合并子列表，尤其是当一个子列表先于另一个耗尽时。始终比较两个子列表的当前元素并追加较小的那个，然后复制剩余的任何元素。

Finally, when comparing algorithms, don’t just state the Big O notation—explain what it means in practical terms. Relate it to the number of comparisons or swaps, and consider both worst-case and best-case scenarios.

最后，在比较算法时，不要只是陈述大 O 表示法——要用实践术语解释其含义。将其与比较或交换的次数联系起来，并考虑最坏情况和最好情况。

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

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

Sorting Algorithms Explained | 排序算法考点精讲