Sorting Algorithms: IGCSE WJEC Computer Science Revision | IGCSE WJEC 计算机：排序考点精讲

📚 Sorting Algorithms: IGCSE WJEC Computer Science Revision | IGCSE WJEC 计算机：排序考点精讲

Sorting is a fundamental concept in computer science, essential for organising data efficiently. In the IGCSE WJEC Computer Science specification, you need to understand how different sorting algorithms work, their step-by-step processes, and their relative efficiency. This guide covers bubble sort, insertion sort, selection sort, and merge sort – the four most commonly examined algorithms – with clear explanations, worked examples, and comparisons to help you master this topic.

排序是计算机科学中的一个基础概念，对高效组织数据至关重要。在 IGCSE WJEC 计算机科学考纲中，你需要了解不同排序算法的工作原理、逐步执行的过程及其相对效率。本指南涵盖冒泡排序、插入排序、选择排序和归并排序——这四种最常见的考点算法，并通过清晰的解释、示例演练和对比帮助你掌握这一主题。

1. Introduction to Sorting | 排序简介

Sorting refers to the process of arranging items in a list or array into a particular order, typically ascending (smallest to largest) or descending (largest to smallest). The items could be numbers, characters, or strings, and they are compared using a defined ordering relation. Sorting makes data easier to search, display, and analyse.

排序是指将列表或数组中的项目按照特定顺序排列的过程，通常是升序（从最小到最大）或降序（从最大到最小）。这些项目可以是数字、字符或字符串，并使用定义的排序关系进行比较。排序使数据更容易搜索、显示和分析。

2. Why Sorting Matters | 排序的重要性

Sorted data is the backbone of efficient algorithms. For example, binary search – which repeatedly divides a sorted dataset in half – is exponentially faster than linear search on unsorted data. Databases, file systems, and many applications rely on sorting to present information logically. Understanding sorting algorithms also builds problem-solving skills, as you learn to compare time complexity and memory usage of different approaches.

排序后的数据是高效算法的基石。例如，二分查找——它反复将已排序数据集对半分——比在未排序数据上进行线性查找快指数级别。数据库、文件系统和许多应用程序都依赖排序来合理呈现信息。理解排序算法还能培养解决问题的能力，因为你可以学习比较不同方法的时间复杂度和内存使用情况。

3. Bubble Sort Algorithm | 冒泡排序算法

Bubble sort works by repeatedly stepping through a 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 means the list is sorted. It is called “bubble sort” because smaller elements “bubble” to the top (beginning) of the list, just as bubbles rise in water.

冒泡排序的工作原理是反复遍历列表，比较相邻元素，并在顺序错误时交换它们。遍历列表的过程不断重复，直到没有需要交换的元素，这意味着列表已排序。之所以称为“冒泡排序”，是因为较小的元素会像水中的气泡一样“冒”到列表的顶部（开头）。

The algorithm can be described in the following steps:

算法可以用以下步骤描述：

Start from the first element, compare it with the next element.
If the current element is greater than the next element (for ascending order), swap them.
Move to the next pair of adjacent elements and repeat the comparison and possible swap.
Continue until the end of the list is reached. This completes one pass.
Repeat the passes until a complete pass is made without any swaps.

从第一个元素开始，将其与下一个元素进行比较。
如果当前元素大于下一个元素（对于升序排列），则交换它们。
移动到下一对相邻元素，重复比较和可能的交换。
继续直到达到列表末尾。这就完成了一次遍历。
重复遍历，直到完成一次没有任何交换的完整遍历。

4. Bubble Sort Walkthrough | 冒泡排序演练

Consider sorting the following list in ascending order: [5, 3, 8, 1, 2].

考虑按升序排列以下列表：[5, 3, 8, 1, 2]。

Pass 1:
Compare 5 and 3: swap → [3, 5, 8, 1, 2]
Compare 5 and 8: no swap → [3, 5, 8, 1, 2]
Compare 8 and 1: swap → [3, 5, 1, 8, 2]
Compare 8 and 2: swap → [3, 5, 1, 2, 8]
End of pass 1; the largest element (8) is now at its correct position.

第一次遍历：
比较 5 和 3：交换 → [3, 5, 8, 1, 2]
比较 5 和 8：不交换 → [3, 5, 8, 1, 2]
比较 8 和 1：交换 → [3, 5, 1, 8, 2]
比较 8 和 2：交换 → [3, 5, 1, 2, 8]
第一次遍历结束；最大元素 (8) 现在已在其正确位置。

Pass 2:
[3, 5, 1, 2, 8] → compare 3 and 5: no swap
Compare 5 and 1: swap → [3, 1, 5, 2, 8]
Compare 5 and 2: swap → [3, 1, 2, 5, 8]
(No need to compare 5 and 8 as 8 is already sorted) End of pass 2.

第二次遍历：
[3, 5, 1, 2, 8] → 比较 3 和 5：不交换
比较 5 和 1：交换 → [3, 1, 5, 2, 8]
比较 5 和 2：交换 → [3, 1, 2, 5, 8]
（无需比较 5 和 8，因为 8 已排序）第二次遍历结束。

Pass 3:
[3, 1, 2, 5, 8] → compare 3 and 1: swap → [1, 3, 2, 5, 8]
Compare 3 and 2: swap → [1, 2, 3, 5, 8]
End of pass 3. No swaps in pass 4, so the list is sorted.

第三次遍历：
[3, 1, 2, 5, 8] → 比较 3 和 1：交换 → [1, 3, 2, 5, 8]
比较 3 和 2：交换 → [1, 2, 3, 5, 8]
第三次遍历结束。第四次遍历中没有交换，因此列表已排序。

5. Insertion Sort Algorithm | 插入排序算法

Insertion sort builds the final sorted array one item at a time. It works similarly to the way you might sort playing cards in your hands. The list is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part, shifting larger elements to the right as needed.

插入排序一次一个元素地构建最终的有序数组。它的工作方式类似于你手中整理扑克牌的方式。列表被虚拟地分为已排序部分和未排序部分。从未排序部分取出值，并放置在已排序部分的正确位置，必要时将较大的元素向右移动。

The algorithm steps are:

算法步骤如下：

Start with the second element (index 1). Assume the first element is sorted.
Compare the current element with the elements in the sorted part (to its left).
Shift all larger elements one position to the right to make space.
Insert the current element into the correct position.
Move to the next element and repeat until the entire list is sorted.

从第二个元素（索引 1）开始。假设第一个元素已排序。
将当前元素与已排序部分（其左侧）中的元素进行比较。
将所有较大的元素向右移动一个位置以腾出空间。
将当前元素插入到正确位置。
移动到下一个元素并重复，直到整个列表排序完毕。

6. Insertion Sort Walkthrough | 插入排序演练

Sort [5, 3, 8, 1, 2] in ascending order using insertion sort.

使用插入排序按升序排列 [5, 3, 8, 1, 2]。

Initial: sorted part = [5], unsorted part = [3, 8, 1, 2].

Take 3 (index 1): compare with 5, 5 > 3, shift 5 right → [ , 5, 8, 1, 2] then insert 3 → [3, 5, 8, 1, 2]

初始：已排序部分 = [5]，未排序部分 = [3, 8, 1, 2]。

取 3（索引 1）：与 5 比较，5 > 3，将 5 右移 → [ , 5, 8, 1, 2] 然后插入 3 → [3, 5, 8, 1, 2]

Take 8 (index 2): compare with 5, 5 < 8, so no shift needed, insert 8 → [3, 5, 8, 1, 2]

取 8（索引 2）：与 5 比较，5 < 8，因此无需移位，插入 8 → [3, 5, 8, 1, 2]

Take 1 (index 3): compare with 8 (shift), 5 (shift), 3 (shift) → [ , , , 3, 5, 8, 2] insert 1 → [1, 3, 5, 8, 2]

取 1（索引 3）：与 8 比较（移位），5（移位），3（移位） → 插入 1 → [1, 3, 5, 8, 2]

Take 2 (index 4): compare with 8 (shift), 5 (shift), 3 (shift), 1 (no shift) → insert 2 → [1, 2, 3, 5, 8]. Sorted.

取 2（索引 4）：与 8 比较（移位），5（移位），3（移位），1（不移位） → 插入 2 → [1, 2, 3, 5, 8]。排序完成。

7. Selection Sort Algorithm | 选择排序算法

Selection sort divides the input list into two parts: a sorted sublist built from left to right and an unsorted sublist containing the remaining elements. The algorithm repeatedly finds the smallest (or largest) element from the unsorted sublist and swaps it with the leftmost unsorted element, moving the boundary of the sorted sublist one element right.

选择排序将输入列表分为两部分：从左到右构建的已排序子列表，以及包含剩余元素的未排序子列表。该算法反复从未排序子列表中找到最小（或最大）元素，并将其与最左边的未排序元素交换，将已排序子列表的边界向右移动一个元素。

The steps are:

步骤如下：

Set a marker for the first unsorted position (initially index 0).
Find the index of the minimum value in the unsorted part.
Swap the found minimum element with the element at the marker position.
Move the marker one position to the right.
Repeat until the entire list is sorted.

为第一个未排序位置设置标记（初始为索引 0）。
找到未排序部分中最小值的索引。
将找到的最小元素与标记位置的元素交换。
将标记向右移动一个位置。
重复直到整个列表排序完毕。

8. Selection Sort Walkthrough | 选择排序演练

Sort [5, 3, 8, 1, 2] using selection sort (ascending).

使用选择排序（升序）对 [5, 3, 8, 1, 2] 进行排序。

Marker at index 0: find min in [5, 3, 8, 1, 2] → 1 at index 3. Swap with index 0 → [1, 3, 8, 5, 2]

标记在索引 0：在 [5, 3, 8, 1, 2] 中找到最小值 1 位于索引 3。与索引 0 交换 → [1, 3, 8, 5, 2]

Marker at index 1: unsorted part [3, 8, 5, 2] min is 2 at index 4. Swap → [1, 2, 8, 5, 3]

标记在索引 1：未排序部分 [3, 8, 5, 2] 最小值为 2 位于索引 4。交换 → [1, 2, 8, 5, 3]

Marker at index 2: unsorted [8, 5, 3] min is 3 at index 4. Swap with index 2 → [1, 2, 3, 5, 8]

标记在索引 2：未排序 [8, 5, 3] 最小值为 3 位于索引 4。与索引 2 交换 → [1, 2, 3, 5, 8]

Marker at index 3: unsorted [5, 8] min is 5, already in place. No swap needed. Sorted in n-1 passes.

标记在索引 3：未排序 [5, 8] 最小值为 5，已在正确位置。无需交换。经过 n-1 次遍历后排序完成。

9. Merge Sort Algorithm | 归并排序算法

Merge sort is a divide-and-conquer algorithm that splits a list into two halves, recursively sorts each half, and then merges the two sorted halves into a single sorted list. It is much more efficient than the previous three algorithms for large datasets and is a stable sort.

归并排序是一种分治算法，它将列表分成两半，递归地对每一半进行排序，然后将两个已排序的半部分合并成一个有序列表。对于大数据集，它的效率远高于前面三种算法，并且是一种稳定排序。

Steps:

If the list has fewer than two elements, it is already sorted; return it.
Divide the list into two roughly equal halves.
Recursively apply merge sort to the left half.
Recursively apply merge sort to the right half.
Merge the two sorted halves: compare the smallest elements of each half and append the smaller one to the result, repeating until one half is exhausted; then append the remaining elements of the other half.

步骤：

如果列表元素少于两个，则已经有序；直接返回。
将列表分成大致相等的两半。
递归地对左半部分应用归并排序。
递归地对右半部分应用归并排序。
合并两个有序半部分：比较每半部分的最小元素，将较小的元素添加到结果中，重复直到某半部分耗尽；然后追加另一半的剩余元素。

10. Merge Sort Walkthrough | 归并排序演练

Sort [5, 3, 8, 1, 2, 7] using merge sort (ascending).

使用归并排序（升序）对 [5, 3, 8, 1, 2, 7] 进行排序。

Divide:

[5, 3, 8, 1, 2, 7] → left [5, 3, 8] and right [1, 2, 7].

划分：

[5, 3, 8, 1, 2, 7] → 左 [5, 3, 8] 和右 [1, 2, 7]。

Left half [5, 3, 8]: divide into [5] and [3, 8]. [5] is sorted. [3, 8] divides into [3] and [8] – both sorted. Merge [3] and [8] → [3, 8]. Merge [5] and [3, 8]: compare 5 and 3 → 3, then 5 and 8 → 5, then 8 → [3, 5, 8].

左半部分 [5, 3, 8]： 划分为 [5] 和 [3, 8]。[5] 已排序。[3, 8] 划分为 [3] 和 [8] —— 两者都已排序。合并 [3] 和 [8] → [3, 8]。合并 [5] 和 [3, 8]：比较 5 和 3 → 3，然后 5 和 8 → 5，然后 8 → [3, 5, 8]。

Right half [1, 2, 7]: divide into [1] and [2, 7]. [2, 7] divides into [2] and [7]. Merge [2] and [7] → [2, 7]. Merge [1] and [2, 7]: 1 first, then 2, then 7 → [1, 2, 7].

右半部分 [1, 2, 7]： 划分为 [1] 和 [2, 7]。[2, 7] 划分为 [2] 和 [7]。合并 [2] 和 [7] → [2, 7]。合并 [1] 和 [2, 7]：先 1，然后 2，然后 7 → [1, 2, 7]。

Final merge of [3, 5, 8] and [1, 2, 7]: compare 3 and 1 → 1, 3 and 2 → 2, 3 and 7 → 3, 5 and 7 → 5, 8 and 7 → 7, then 8 → [1, 2, 3, 5, 7, 8]. Fully sorted.

最终合并 [3, 5, 8] 和 [1, 2, 7]：比较 3 和 1 → 1，3 和 2 → 2，3 和 7 → 3，5 和 7 → 5，8 和 7 → 7，然后 8 → [1, 2, 3, 5, 7, 8]。完全排序。

11. Comparing Sorting Algorithms | 排序算法比较

Different sorting algorithms have different efficiencies, usually measured by time complexity (number of comparisons/swaps) and space complexity (extra memory used). In IGCSE WJEC, you are expected to compare them qualitatively and with reference to Big O notation.

不同的排序算法有不同的效率，通常用时间复杂度（比较/交换的次数）和空间复杂度（使用的额外内存）来衡量。在 IGCSE WJEC 中，你需要进行定性比较，并参考大 O 表示法进行比较。

Algorithm	Best Case	Average Case	Worst Case	Space Complexity	Stable?
Bubble Sort	O(n)	O(n²)	O(n²)	O(1)	Yes
Insertion Sort	O(n)	O(n²)	O(n²)	O(1)	Yes
Selection Sort	O(n²)	O(n²)	O(n²)	O(1)	No
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)	Yes

Bubble, insertion, and selection sorts are simple but inefficient for large lists (O(n²) in average/worst case). Merge sort is significantly faster with O(n log n) time but requires additional memory for merging. Insertion sort performs very well on small or nearly sorted data.

冒泡排序、插入排序和选择排序简单易懂，但对于大型列表效率较低（平均/最坏情况下为 O(n²)）。归并排序速度快得多，时间复杂度为 O(n log n)，但需要额外的内存进行合并。插入排序在处理小规模或接近有序的数据时表现非常出色。

12. Choosing the Right Sort | 选择合适的排序

There is no single best sorting algorithm; the choice depends on the specific requirements. Consider the following scenarios:

Small datasets (n < 50): Insertion sort or selection sort is often sufficient and simple to implement.
Nearly sorted data: Insertion sort works in near O(n) time and bubble sort can stop early.
Large unsorted data: Merge sort is preferred due to its O(n log n) guaranteed time complexity.
Memory constraints: Bubble, insertion, or selection sort use O(1) extra space, while merge sort requires O(n) auxiliary storage.
Stability needed: If the relative order of equal elements must be preserved, use a stable sort (bubble, insertion, merge). Selection sort is not stable.

没有一种绝对最佳的排序算法；选择取决于具体需求。考虑以下情形：

小数据集（n < 50）： 插入排序或选择排序通常足够且易于实现。
接近有序的数据： 插入排序几乎以 O(n) 时间运行，冒泡排序可以提前终止。
大型无序数据： 优先选择归并排序，因为它具有保证的 O(n log n) 时间复杂度。
内存限制： 冒泡、插入或选择排序使用 O(1) 额外空间，而归并排序需要 O(n) 辅助存储。
需要稳定性： 如果必须保持相等元素的相对顺序，则使用稳定排序（冒泡、插入、归并）。选择排序不稳定。

Mastering these sorting algorithms and their trade-offs will not only prepare you for IGCSE exam questions but also build a solid foundation for further study in computer science.

掌握这些排序算法及其权衡，不仅能帮助你应对 IGCSE 考试题目，还能为进一步学习计算机科学打下坚实基础。

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

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

Sorting Algorithms: IGCSE WJEC Computer Science Revision | IGCSE WJEC 计算机：排序 考点精讲