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

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

Sorting algorithms are a fundamental part of the WJEC GCSE Computer Science specification. They appear in both paper-based exam questions and practical programming scenarios. Understanding how to compare, trace, and implement sorting algorithms is essential. This article breaks down the key sorting methods you need to know, including bubble sort, insertion sort, and merge sort, with clear explanations in both English and Chinese.

排序算法是 WJEC GCSE 计算机科学考试大纲中的基础内容。无论是笔试题目还是实际编程场景，排序都频繁出现。理解如何比较、跟踪和实现排序算法至关重要。本文详细拆解你需要掌握的关键排序方法，包括冒泡排序、插入排序和归并排序，并配以中英文清晰讲解。

1. What is a Sorting Algorithm? | 什么是排序算法？

A sorting algorithm puts elements of a list into a specific order, such as ascending (smallest to largest) or descending (largest to smallest). The data can be numbers, strings, or any comparable items. Efficient sorting is important because many other algorithms, like binary search, require sorted data.

排序算法将列表元素按特定顺序排列，例如升序（从小到大）或降序（从大到小）。数据可以是数字、字符串或任何可比较的项。高效的排序很重要，因为许多其他算法（如二分查找）要求数据已排序。

In WJEC Computer Science, you are expected to know how several classic sorting algorithms work, trace through them step by step, and compare their efficiency in terms of the number of comparisons or swaps they make.

在 WJEC 计算机科学中，你需要了解几种经典排序算法的工作原理，能够逐步跟踪它们的执行过程，并从比较次数或交换次数的角度比较其效率。

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

Bubble sort repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, meaning the list is sorted. It is called ‘bubble’ sort because smaller elements ‘bubble’ to the top (beginning of the list) like bubbles in water.

冒泡排序反复遍历列表，比较相邻元素，如果顺序错误则交换它们。遍历列表的过程不断重复，直到不需要交换为止，这意味着列表已排序。它被称为“冒泡”排序，是因为较小的元素像水中的气泡一样“冒”到列表的顶端（开头）。

During each pass, the largest unsorted element moves to its correct position at the end. This means after the first pass, the last element is sorted; after the second pass, the last two elements are sorted, and so on. The algorithm can be made more efficient by stopping early if a complete pass occurs with no swaps.

在每一轮遍历中，最大的未排序元素会移动到末尾的正确位置。这意味着第一轮遍历后，最后一个元素已排序；第二轮遍历后，最后两个元素已排序，依此类推。如果在某轮完整遍历中没有发生交换，算法可以提前停止，从而提高效率。

Pseudocode for bubble sort (ascending):

冒泡排序伪代码（升序）：

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

3. Tracing Bubble Sort with an Example | 用示例跟踪冒泡排序

Consider sorting the list [4, 2, 5, 1, 3] in ascending order. During the first pass, we compare and swap adjacent elements from left to right:

考虑将列表 [4, 2, 5, 1, 3] 按升序排序。在第一轮遍历中，我们从左到右比较并交换相邻元素：

Compare 4 and 2 → swap → [2, 4, 5, 1, 3]
Compare 4 and 5 → no swap → [2, 4, 5, 1, 3]
Compare 5 and 1 → swap → [2, 4, 1, 5, 3]
Compare 5 and 3 → swap → [2, 4, 1, 3, 5]

比较 4 和 2 → 交换 → [2, 4, 5, 1, 3]
比较 4 和 5 → 不交换 → [2, 4, 5, 1, 3]
比较 5 和 1 → 交换 → [2, 4, 1, 5, 3]
比较 5 和 3 → 交换 → [2, 4, 1, 3, 5]

After the first pass, the largest element (5) is in its correct final position. The second pass starts again from the beginning, but we can ignore the last element. The process repeats until the list is fully sorted. Tracing tables are often used in exams to record each step.

第一轮遍历后，最大的元素 (5) 位于其正确的最终位置。第二轮遍历再次从头开始，但我们可以忽略最后一个元素。这个过程不断重复，直到列表完全排序。考试中常使用跟踪表来记录每一步。

4. Efficiency of Bubble Sort | 冒泡排序的效率

Bubble sort is easy to understand but inefficient for large datasets. In the worst case (a reversed list), the number of comparisons is roughly n²/2, where n is the number of items. This is because there are n-1 passes and about n/2 comparisons per pass on average. Its time complexity is O(n²).

冒泡排序易于理解，但对大数据集效率低下。在最坏情况下（列表完全逆序），比较次数大约为 n²/2，其中 n 是元素个数。这是因为大约有 n-1 轮遍历，而每轮平均进行约 n/2 次比较。其时间复杂度为 O(n²)。

The space complexity is O(1) because it sorts the list in place, using only a small amount of extra memory for swapping. In exam questions, you may be asked to count the total number of comparisons or swaps for a given list.

空间复杂度为 O(1)，因为它在原地排序，只使用少量额外内存进行交换。在考试题目中，你可能会被要求计算给定列表的总比较次数或交换次数。

5. Insertion Sort – Building the Sorted List | 插入排序 – 构建已排序列表

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

插入排序每次将一个元素从未排序部分取出，并将其插入到已排序部分的正确位置。这类似于对手中扑克牌排序的方式：你拿起一张牌，将其插入到手中已有牌的适当位置。

The algorithm starts by assuming the first element is trivially sorted. It then looks at the next element and compares it with the sorted elements, shifting them to the right as necessary to make room for the new element. This process continues until the whole list is sorted.

算法开始时假设第一个元素是已排序的。然后查看下一个元素，将其与已排序的部分比较，必要时将已排序元素向右移动，为新元素腾出空间。这个过程持续进行，直到整个列表排序完毕。

Pseudocode for insertion sort (ascending):

插入排序伪代码（升序）：

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

6. Tracing Insertion Sort | 跟踪插入排序

Let’s trace insertion sort on the list [4, 2, 5, 1, 3]. We start with the first element (4) considered sorted. i=1, key=2: compare with 4, shift 4 to the right, insert 2 → [2, 4, 5, 1, 3]. i=2, key=5: 5 > 4, so it stays → [2, 4, 5, 1, 3]. i=3, key=1: compare with 5, shift right; compare with 4, shift right; compare with 2, shift right; insert 1 → [1, 2, 4, 5, 3]. i=4, key=3: compare with 5, shift; compare with 4, shift; insert 3 → [1, 2, 3, 4, 5].

让我们跟踪列表 [4, 2, 5, 1, 3] 的插入排序。我们将第一个元素 (4) 视为已排序。i=1, key=2：与 4 比较，将 4 右移，插入 2 → [2, 4, 5, 1, 3]。i=2, key=5：5 > 4，保持不变 → [2, 4, 5, 1, 3]。i=3, key=1：与 5 比较，右移；与 4 比较，右移；与 2 比较，右移；插入 1 → [1, 2, 4, 5, 3]。i=4, key=3：与 5 比较，右移；与 4 比较，右移；插入 3 → [1, 2, 3, 4, 5]。

Notice that insertion sort often requires fewer comparisons than bubble sort in practice, especially when the list is partially sorted. However, in the worst case, it still has a time complexity of O(n²).

请注意，在实践中插入排序通常比冒泡排序需要更少的比较，尤其是当列表部分有序时。然而，在最坏情况下，其时间复杂度仍为 O(n²)。

7. Merge Sort – The Divide-and-Conquer Algorithm | 归并排序 – 分治算法

Merge sort is a more efficient, recursive algorithm that uses a divide-and-conquer strategy. It divides 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 there is only one sublist remaining – the fully sorted list.

归并排序是一种更高效的递归算法，采用分治策略。它将未排序的列表分成 n 个子列表，每个子列表包含一个元素（单个元素自然有序）。然后反复合并子列表，生成新的有序子列表，直到只剩下一个子列表，即完全排序的列表。

The merging step is key: it takes two sorted sublists and combines them into one sorted list by repeatedly comparing the smallest remaining elements of each sublist and taking the smaller one.

合并步骤是关键：它取两个有序子列表，通过反复比较每个子列表中最小的剩余元素并取出较小的那个，将它们合并为一个有序列表。

Pseudocode for merge sort:

归并排序伪代码：

MERGE_SORT(list)
  IF length(list) <= 1 THEN return list
  mid ← length(list)/2
  left ← MERGE_SORT(list[0..mid-1])
  right ← MERGE_SORT(list[mid..end])
  return MERGE(left, right)

8. Tracing Merge Sort | 跟踪归并排序

Applying merge sort to [4, 2, 5, 1, 3]:
Split: [4,2,5] and [1,3] → continue splitting → [4,2] and [5] for left; [1] and [3] for right → further split [4,2] into [4] and [2].
Merge: merge [4] and [2] → [2,4]; merge with [5] → [2,4,5]. Merge [1] and [3] → [1,3]. Finally merge [2,4,5] and [1,3]: compare 2 and 1 → take 1; compare 2 and 3 → take 2; compare 4 and 3 → take 3; compare 4 and (no more in right) → take 4; take 5 → [1,2,3,4,5].

对 [4, 2, 5, 1, 3] 应用归并排序：
拆分：[4,2,5] 和 [1,3] → 继续拆分 → 左侧 [4,2] 和 [5]；右侧 [1] 和 [3] → 进一步将 [4,2] 拆分为 [4] 和 [2]。
合并：合并 [4] 和 [2] → [2,4]；与 [5] 合并 → [2,4,5]。合并 [1] 和 [3] → [1,3]。最后合并 [2,4,5] 和 [1,3]：比较 2 和 1 → 取出 1；比较 2 和 3 → 取出 2；比较 4 和 3 → 取出 3；比较 4 和右侧无剩余 → 取出 4；取出 5 → [1,2,3,4,5]。

Merge sort’s time complexity is O(n log n) in all cases, which is significantly better than O(n²) for large datasets. However, it requires additional memory for the temporary sublists, so its space complexity is O(n).

归并排序在所有情况下的时间复杂度都是 O(n log n)，对于大数据集这远优于 O(n²)。但它需要为临时子列表分配额外的内存，因此空间复杂度为 O(n)。

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

When choosing a sorting algorithm, you need to consider time complexity (how it scales with input size) and space complexity (extra memory required). Bubble sort and insertion sort are simple and use little memory, but they are slow for large lists. Merge sort is faster for large lists but uses more memory.

在选择排序算法时，你需要考虑时间复杂度（随输入规模的增长情况）和空间复杂度（所需的额外内存）。冒泡排序和插入排序简单且内存占用少，但对于大列表速度慢。归并排序对于大列表速度更快，但需要更多内存。

Algorithm	Best time	Average time	Worst time	Space	Stable?
Bubble	O(n)	O(n²)	O(n²)	O(1)	Yes
Insertion	O(n)	O(n²)	O(n²)	O(1)	Yes
Merge	O(n log n)	O(n log n)	O(n log n)	O(n)	Yes

Stable means that two equal elements retain their original relative order.

稳定意味着两个相等元素保留其原始相对顺序。

10. Exam Tips for Sorting Questions | 排序题目应试技巧

In WJEC GCSE exams, sorting algorithm questions often ask you to complete a trace table showing the state of the list after each pass or swap. You must carefully follow the algorithm step by step, not jump to the final sorted list too quickly. Marks are awarded for showing correct intermediate steps, not just the final answer.

在 WJEC GCSE 考试中，排序算法题目经常要求你完成一个跟踪表，显示每轮遍历或交换后列表的状态。你必须仔细地一步一步遵循算法，不要急于跳到最终排序列表。中间步骤的正确展示会得分，而不仅仅是最终答案。

You may also be asked to compare algorithms, explain why one is more efficient for a particular data set, or identify the number of comparisons made. Being able to write pseudocode or understand a given pseudocode is crucial. Practice with small lists of 5-6 elements until you can confidently trace each algorithm.

你还可能被要求比较算法，解释为什么某种算法对特定数据集更高效，或识别比较次数。能够编写伪代码或理解给定的伪代码至关重要。用 5-6 个元素的短列表进行练习，直到你能自信地跟踪每种算法。

11. Common Misconceptions | 常见误区

A common mistake is thinking bubble sort compares each element with every other element. It only ever compares adjacent elements. Another misconception is that merge sort splits the list into two halves once and then sorts them – it actually keeps splitting recursively until single elements remain. Finally, many students confuse the space complexity of merge sort with that of the other two; remember merge sort needs extra memory proportional to the list size.

一个常见错误是认为冒泡排序会比较每个元素与所有其他元素。它实际上只比较相邻元素。另一个误解是认为归并排序只将列表分成两半一次然后对它们排序——实际上它会递归地持续拆分，直到只剩下单个元素。最后，许多学生容易混淆归并排序与其他两种算法的空间复杂度；请记住归并排序需要与列表大小成比例的额外内存。

12. Programming Implementation Practice | 编程实现练习

While the exam is mostly paper-based, you may have to interpret or write small code snippets. Implement all three sorting algorithms in your chosen language (Python is common in WJEC). Test them with edge cases: an already sorted list, a reverse sorted list, and a list with repeated elements. Count the number of comparisons to verify your understanding of efficiency.

虽然考试主要是笔试，但你可能需要解释或编写短小的代码片段。用你选择的语言（WJEC 常使用 Python）实现所有三种排序算法。使用边界情况进行测试：已排序的列表、逆序列表和包含重复元素的列表。计算比较次数以验证你对效率的理解。

For example, in Python, bubble sort can be written with nested loops and a boolean flag to detect early completion. This hands-on practice will deepen your understanding and make exam tracing tasks feel more natural.

例如，在 Python 中，冒泡排序可以用嵌套循环和一个布尔标志来检测提前完成。这种动手实践将加深你的理解，让考试中的跟踪任务感觉更自然。

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

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

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