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

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

Sorting is a fundamental operation in computer science that arranges data into a meaningful order, typically ascending or descending. Understanding how different sorting algorithms work, their efficiency, and their use cases is a key component of the IGCSE OCR Computer Science syllabus. This article provides a comprehensive revision guide covering bubble sort, insertion sort, and merge sort, complete with worked examples, pseudocode, and comparisons.

排序是计算机科学中的一项基本操作，它将数据排列成有意义的顺序，通常是升序或降序。理解不同排序算法的工作原理、效率及其应用场景，是 IGCSE OCR 计算机科学课程的重要组成部分。本文提供全面的复习指南，涵盖冒泡排序、插入排序和归并排序，并配有完整示例、伪代码和对比分析。

1. Introduction to Sorting Algorithms | 排序算法简介

A sorting algorithm is a method for reorganising a list of items into a particular order. In IGCSE Computer Science, you need to know how several key algorithms function, be able to trace their execution on a given dataset, and evaluate their performance in terms of time and space complexity.

排序算法是一种将列表中的项目重新组织为特定顺序的方法。在 IGCSE 计算机科学中，你需要了解几种核心算法的工作原理，能够对给定数据集追踪其执行过程，并从时间和空间复杂度的角度评估其性能。

Sorting is essential because it makes searching more efficient and helps organise data for display. The three algorithms required by OCR are bubble sort, insertion sort, and merge sort. Each uses a different strategy to achieve a sorted list.

排序至关重要，因为它能让搜索更高效，并有助于组织数据以供展示。OCR 要求掌握的三种算法是冒泡排序、插入排序和归并排序。每种算法都使用不同的策略来实现有序列表。

2. Key Terminology | 关键术语

Before diving into the algorithms, it is helpful to clarify some common terms. A pass refers to one complete traversal of the list. A comparison checks two elements to decide their relative order. A swap exchanges the positions of two elements. The time complexity describes how the execution time grows with input size n, often expressed using Big O notation.

在深入算法之前，明确一些常用术语很有帮助。一趟遍历（pass）指对列表的一次完整遍历。比较（comparison）检查两个元素以确定它们的相对顺序。交换（swap）是指交换两个元素的位置。时间复杂度（time complexity）描述了执行时间如何随输入规模 n 增长，通常用大 O 表示法表示。

We will often use an unsorted list such as [5, 2, 9, 1, 5, 6] to illustrate how each algorithm works. The goal is to produce [1, 2, 5, 5, 6, 9] in ascending order. You may also need to sort in descending order by reversing the comparison condition.

我们通常会使用一个未排序的列表，例如 [5, 2, 9, 1, 5, 6] 来演示每种算法如何工作，目标是生成升序列表 [1, 2, 5, 5, 6, 9]。你也可能需要通过反转比较条件来实现降序排序。

3. Bubble Sort – How It Works | 冒泡排序工作原理

Bubble sort works by repeatedly stepping through the list, comparing adjacent elements and swapping them if they are in the wrong order. The process repeats until a complete pass is made without any swaps, which means the list is sorted.

冒泡排序通过重复遍历列表，比较相邻的元素，如果顺序错误就交换它们。这个过程不断重复，直到某次完整遍历中没有发生任何交换，这意味着列表已经有序。

Imagine the largest element ‘bubbling up’ to the end of the list during the first pass, just like a bubble rising in liquid. In each subsequent pass, the next largest unsorted element moves to its correct position, so the algorithm effectively builds the sorted portion from the right.

想象最大的元素在第一次遍历时像液体中的气泡一样“冒泡”到列表末尾。在接下来的每次遍历中，下一个最大的未排序元素会移动到它正确的位置，因此该算法实际上是从右往左逐步构建已排序的部分。

For an array of n elements, bubble sort requires up to n−1 passes. However, an early exit condition (no swaps in a pass) can stop the algorithm early, making it adaptive.

对于一个包含 n 个元素的数组，冒泡排序最多需要 n−1 次遍历。不过，可以通过提前退出条件（某次遍历无交换）来提前终止算法，这使其具有自适应性。

4. Bubble Sort – Worked Example | 冒泡排序示例

Let us trace bubble sort on the list [5, 2, 9, 1, 5, 6]. We want ascending order, so we swap when the left element is greater than the right one.

让我们在列表 [5, 2, 9, 1, 5, 6] 上追踪冒泡排序。我们需要升序排列，因此当左元素大于右元素时进行交换。

Pass 1: Compare 5 and 2 → swap → [2, 5, 9, 1, 5, 6]. Compare 5 and 9 → no swap. Compare 9 and 1 → swap → [2, 5, 1, 9, 5, 6]. Compare 9 and 5 → swap → [2, 5, 1, 5, 9, 6]. Compare 9 and 6 → swap → [2, 5, 1, 5, 6, 9]. End of pass 1; largest element 9 is in place.

第 1 趟：比较 5 和 2 → 交换 → [2, 5, 9, 1, 5, 6]。比较 5 和 9 → 不交换。比较 9 和 1 → 交换 → [2, 5, 1, 9, 5, 6]。比较 9 和 5 → 交换 → [2, 5, 1, 5, 9, 6]。比较 9 和 6 → 交换 → [2, 5, 1, 5, 6, 9]。第 1 趟结束，最大元素 9 已到位。

Pass 2: [2, 5, 1, 5, 6, 9] → compare 2 and 5, no swap. Compare 5 and 1 → swap → [2, 1, 5, 5, 6, 9]. Compare 5 and 5, no swap. Compare 5 and 6, no swap. Compare 6 and 9, no swap. End; now 6 and 9 are in final positions. Continue: Pass 3: [2, 1, 5, 5, 6, 9] → swap 2 and 1 → [1, 2, 5, 5, 6, 9]. Pass 4: no swaps, sorted.

第 2 趟：[2, 5, 1, 5, 6, 9] → 比较 2 和 5，不交换。比较 5 和 1 → 交换 → [2, 1, 5, 5, 6, 9]。比较 5 和 5，不交换。比较 5 和 6，不交换。比较 6 和 9，不交换。结束；现在 6 和 9 处于最终位置。继续：第 3 趟：[2, 1, 5, 5, 6, 9] → 交换 2 和 1 → [1, 2, 5, 5, 6, 9]。第 4 趟：无交换，已排序。

You should be able to show each pass like this in an exam. Note that the number of comparisons decreases each pass because the largest elements are already in place.

在考试中你应该能够像这样展示每一趟的过程。注意，每趟的比较次数会减少，因为最大的元素已经就位。

5. Bubble Sort – Pseudocode and Efficiency | 冒泡排序伪代码与效率

Pseudocode for bubble sort is straightforward and often appears in OCR exam papers. A typical representation is:

冒泡排序的伪代码很直观，经常出现在 OCR 试卷中。一个典型的表示如下：

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

An optimised version includes a flag to detect early completion, breaking the outer loop if no swaps occur in a full pass.

优化版本包含一个标志位来检测是否提前完成，如果在一次完整遍历中没有发生交换，则跳出外部循环。

The time complexity of bubble sort in the worst and average cases is O(n²) because there are two nested loops. In the best case, when the list is already sorted, the optimised version achieves O(n). Space complexity is O(1) as it sorts in-place.

冒泡排序的最坏和平均时间复杂度为 O(n²)，因为存在两层嵌套循环。在最好情况下，即列表已经有序时，优化版本可以达到 O(n)。空间复杂度为 O(1)，因为它原地排序。

6. Insertion Sort – How It Works | 插入排序工作原理

Insertion sort builds the final sorted list one element at a time. It works by taking each element from the unsorted part and inserting it into its correct position within the sorted part, shifting elements as necessary.

插入排序每次一个元素地构建最终的有序列表。它从无序部分取出每个元素，并将其插入到有序部分的正确位置，必要时移动元素。

Think of how you might sort a hand of playing cards: you pick up one card at a time and insert it into the appropriate spot among the cards already in your hand. This is exactly the approach insertion sort uses.

想象你如何整理一手扑克牌：你每次捡起一张牌，并将其插入手中已有牌中的合适位置。这正是插入排序采用的方法。

Initially, the first element is considered sorted. Then, for each next element (key), it compares the key with elements in the sorted part from right to left, moving any larger elements one position to the right until the correct spot is found.

初始时，第一个元素被视为已排序。然后，对于接下来的每个元素（键值），它将键值与已排序部分的元素从右向左比较，将所有较大的元素向右移动一个位置，直到找到正确的位置。

7. Insertion Sort – Worked Example | 插入排序示例

Using the same list [5, 2, 9, 1, 5, 6], we start with sorted part [5] and unsorted [2, 9, 1, 5, 6].

使用相同的列表 [5, 2, 9, 1, 5, 6]，我们从已排序部分 [5] 和无序部分 [2, 9, 1, 5, 6] 开始。

Step 1: key = 2. Compare with 5: 2 < 5, shift 5 right → [5, 5] then place 2 → [2, 5]. Sorted part: [2, 5], unsorted: [9, 1, 5, 6].

步骤 1：键值 = 2。与 5 比较：2 < 5，右移 5 → [5, 5] 然后放入 2 → [2, 5]。已排序部分：[2, 5]，无序部分：[9, 1, 5, 6]。

Step 2: key = 9. Compare with 5: 9 > 5, so 9 stays in place. Sorted part: [2, 5, 9].

步骤 2：键值 = 9。与 5 比较：9 > 5，所以 9 保持在原位。已排序部分：[2, 5, 9]。

Step 3: key = 1. Compare with 9 (shift right), 5 (shift right), 2 (shift right). Place 1 at front → [1, 2, 5, 9]. Sorted part: [1, 2, 5, 9].

步骤 3：键值 = 1。与 9 比较（右移），与 5 比较（右移），与 2 比较（右移）。将 1 放在最前面 → [1, 2, 5, 9]。已排序部分：[1, 2, 5, 9]。

Step 4: key = 5. Compare with 9 (shift), compare with 5: 5 == 5, so insert after the existing 5 → [1, 2, 5, 5, 9].

步骤 4：键值 = 5。与 9 比较（右移），与 5 比较：5 == 5，因此插入到现有 5 之后 → [1, 2, 5, 5, 9]。

Step 5: key = 6. Compare with 9 (shift), compare with 5: 6 > 5, so insert before 9 → [1, 2, 5, 5, 6, 9]. Done.

步骤 5：键值 = 6。与 9 比较（右移），与 5 比较：6 > 5，因此插入到 9 之前 → [1, 2, 5, 5, 6, 9]。完成。

Notice that the insertion operation can shift multiple elements. In an exam, you should clearly show the shifting and insertion.

请注意，插入操作可能会移动多个元素。在考试中，你应该清楚地展示移位和插入过程。

8. Insertion Sort – Pseudocode and Efficiency | 插入排序伪代码与效率

The standard pseudocode for insertion sort is as follows:

插入排序的标准伪代码如下：

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

Like bubble sort, insertion sort has a worst-case and average time complexity of O(n²) due to the nested loops. However, it is efficient for small datasets and is often used as part of more advanced algorithms. Its best-case time is O(n) when the input is already sorted, and it sorts in-place, so space complexity is O(1).

与冒泡排序类似，由于嵌套循环，插入排序的最坏和平均时间复杂度为 O(n²)。不过，它对小数据集很高效，并常被用作更高级算法的一部分。当输入已经有序时，其最佳时间复杂度为 O(n)，并且它原地排序，因此空间复杂度为 O(1)。

Insertion sort is stable: equal elements retain their relative order. This is important when sorting records with multiple fields.

插入排序是稳定的：相等的元素保持它们的相对顺序。这在按多个字段排序记录时很重要。

9. Merge Sort – How It Works | 归并排序工作原理

Merge sort is a divide-and-conquer algorithm that splits the list into smaller sublists, recursively sorts them, and then merges the sorted sublists back together to produce the final sorted list.

归并排序是一种分治算法，它将列表拆分成较小的子列表，递归地对它们进行排序，然后将已排序的子列表合并在一起，生成最终的有序列表。

The algorithm repeatedly divides the unsorted list into two halves until each sublist contains a single element (which is trivially sorted). Then it merges two adjacent sublists, comparing the smallest elements of each and building a new sorted sublist.

算法重复地将未排序列表分成两半，直到每个子列表只包含一个元素（这自然是已排序的）。然后，它合并两个相邻的子列表，比较每个子列表的最小元素，构建一个新的有序子列表。

Unlike bubble and insertion sorts, merge sort requires additional memory proportional to the size of the list, which makes it less memory-efficient for large lists, but its time complexity is significantly better for large inputs.

与冒泡和插入排序不同，归并排序需要与列表大小成比例的额外内存，这使得它在处理大列表时内存效率较低，但其时间复杂度对于大规模输入要好得多。

10. Merge Sort – Worked Example | 归并排序示例

Let us trace merge sort on [5, 2, 9, 1, 5, 6]. The process is best explained by showing the splitting and merging phases separately.

让我们在 [5, 2, 9, 1, 5, 6] 上追踪归并排序。通过分别展示拆分和合并阶段可以最好地解释这个过程。

Splitting: Divide [5, 2, 9, 1, 5, 6] → left [5, 2, 9] and right [1, 5, 6]. Divide [5, 2, 9] → [5] and [2, 9]; [2, 9] → [2] and [9]. Divide [1, 5, 6] → [1] and [5, 6]; [5, 6] → [5] and [6]. All sublists are now single elements.

拆分：拆分 [5, 2, 9, 1, 5, 6] → 左 [5, 2, 9] 和右 [1, 5, 6]。拆分 [5, 2, 9] → [5] 和 [2, 9]；[2, 9] → [2] 和 [9]。拆分 [1, 5, 6] → [1] 和 [5, 6]；[5, 6] → [5] 和 [6]。现在所有子列表都是单个元素。

Merging: Merge [2] and [9] → compare 2 and 9, resulting in [2, 9]. Merge [5] and [2, 9] → compare 5 and 2, take 2, then 5, then 9 → [2, 5, 9]. On the right side: merge [5] and [6] → [5, 6]. Merge [1] and [5, 6] → compare 1 and 5, take 1, then 5, then 6 → [1, 5, 6]. Finally, merge [2, 5, 9] and [1, 5, 6] → compare 2 and 1 → take 1; compare 2 and 5 → take 2; compare 5 and 5 → take 5 (from left); compare 9 and 5 → take 5 (from right); compare 9 and 6 → take 6; then take 9 → [1, 2, 5, 5, 6, 9].

合并：合并 [2] 和 [9] → 比较 2 和 9，得到 [2, 9]。合并 [5] 和 [2, 9] → 比较 5 和 2，取 2，然后 5，然后 9 → [2, 5, 9]。右侧：合并 [5] 和 [6] → [5, 6]。合并 [1] 和 [5, 6] → 比较 1 和 5，取 1，然后 5，然后 6 → [1, 5, 6]。最后，合并 [2, 5, 9] 和 [1, 5, 6] → 比较 2 和 1 → 取 1；比较 2 和 5 → 取 2；比较 5 和 5 → 取 5（来自左侧）；比较 9 和 5 → 取 5（来自右侧）；比较 9 和 6 → 取 6；然后取 9 → [1, 2, 5, 5, 6, 9]。

You should be able to draw the splitting tree and the merging steps. Note how each merge scans both sublists only once.

你应该能够画出拆分树和合并步骤。注意，每次合并只遍历两个子列表一次。

11. Merge Sort – Pseudocode and Efficiency | 归并排序伪代码与效率

Merge sort is usually expressed with two procedures: one for splitting (mergeSort) and one for merging (merge).

归并排序通常用两个过程来表示：一个用于拆分（mergeSort），一个用于合并（merge）。

PROCEDURE mergeSort(arr)
  IF length(arr) <= 1 THEN RETURN arr
  mid ← length(arr) / 2
  left ← mergeSort(arr[0..mid-1])
  right ← mergeSort(arr[mid..end])
  RETURN merge(left, right)
ENDPROCEDURE

PROCEDURE merge(left, right)
  result ← empty list
  WHILE left AND right are not empty
    IF left[0] <= right[0] THEN
      append left[0] to result; remove left[0]
    ELSE
      append right[0] to result; remove right[0]
    ENDIF
  ENDWHILE
  append remaining elements from left or right
  RETURN result
ENDPROCEDURE

The time complexity of merge sort is O(n log n) in all cases (worst, average, best). This is because the list is halved log n times, and each level of merging requires O(n) operations. Space complexity is O(n) due to auxiliary arrays needed for merging, which makes it less space-efficient than the previous two algorithms.

归并排序在所有情况下（最坏、平均、最好）的时间复杂度均为 O(n log n)。这是因为列表被分成两半 log n 次，而每一层的合并需要 O(n) 次操作。由于需要辅助数组进行合并，空间复杂度为 O(n)，这使其空间效率低于前两种算法。

Merge sort is stable when implemented carefully, which is useful for secondary sorting criteria. It is the preferred sorting method for large datasets where memory is not a primary constraint.

归并排序在谨慎实现时是稳定的，这对于辅助排序条件很有用。它是内存不是主要限制时大规模数据集的首选排序方法。

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

When revising for your IGCSE exam, you must be able to compare these algorithms on several criteria. The table below summarises the key properties.

在准备 IGCSE 考试时，你必须能够从多个方面比较这些算法。下面的表格总结了关键特性。

Algorithm	Time (Best)	Time (Average)	Time (Worst)	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 simple to code and use constant extra memory, but they become slow for large lists. Merge sort is much faster on large inputs, but it uses more memory and requires a more complex implementation. In exams, you might be asked to justify which algorithm to use for a given scenario

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

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

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