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

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

Sorting is a fundamental concept in computer science that arranges data in a specific order, typically ascending or descending. For CIE GCSE Computer Science, you must understand how common sorting algorithms work, be able to trace them step by step, and compare their efficiency. This article covers bubble sort, insertion sort, and merge sort, breaking down every key point you need for the exam.

排序是计算机科学中的基本概念，它按照特定顺序（通常是升序或降序）排列数据。对于 CIE GCSE 计算机科学，你必须理解常见排序算法的工作原理，能够逐步跟踪它们，并比较它们的效率。本文涵盖冒泡排序、插入排序和归并排序，分解考试所需的每一个关键点。

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

Sorting means putting a list of items into a logical order, such as arranging numbers from smallest to largest or arranging strings alphabetically. Sorting makes data easier to search, display, and analyse. Algorithms are step-by-step procedures for sorting data efficiently.

排序意味着将一组项目按逻辑顺序排列，例如将数字从小到大排列，或按字母顺序排列字符串。排序使数据更易于搜索、显示和分析。算法是高效排序数据的逐步过程。

2. Bubble Sort – Basic Idea | 冒泡排序 – 基本思想

Bubble sort works by repeatedly stepping through the list, comparing adjacent elements and swapping them if they are in the wrong order. After each complete pass through the list, the next largest element “bubbles up” to its correct position at the end. The process repeats until no more swaps are needed.

冒泡排序通过反复遍历列表，比较相邻元素，如果顺序错误就交换它们。每完成一次完整的遍历，下一个最大的元素就会“冒泡”到末尾正确的位置。重复此过程，直到不需要再交换为止。

3. Bubble Sort – Step-by-Step Example | 冒泡排序 – 逐步示例

Consider sorting the list [5, 1, 4, 2, 8] in ascending order. First pass: compare 5 and 1 → swap, list becomes [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. After the first pass, the largest element 8 is in place. Second pass: compare 1 and 4 → no swap; compare 4 and 2 → swap → [1, 2, 4, 5, 8]; the rest are already sorted. No swaps in the next pass, so the algorithm stops.

以升序排列列表 [5, 1, 4, 2, 8] 为例。第一趟：比较 5 和 1 → 交换，列表变为 [1, 5, 4, 2, 8]；比较 5 和 4 → 交换 → [1, 4, 5, 2, 8]；比较 5 和 2 → 交换 → [1, 4, 2, 5, 8]；比较 5 和 8 → 不交换。第一趟后，最大元素 8 就位。第二趟：比较 1 和 4 → 不交换；比较 4 和 2 → 交换 → [1, 2, 4, 5, 8]；其余已排序。下一趟没有交换，算法停止。

4. Bubble Sort – Algorithm and Pseudocode | 冒泡排序 – 算法与伪代码

The algorithm uses two nested loops. The outer loop controls the number of passes (n-1 for a list of length n). The inner loop compares adjacent items and swaps if needed. A common optimisation is to stop early if no swaps occur during a pass, using a flag variable.

该算法使用两个嵌套循环。外层循环控制遍历次数（长度为 n 的列表需 n-1 次）。内层循环比较相邻项，并在需要时交换。一种常见的优化是如果一趟中没有发生交换，就提前停止，使用一个标志变量。

PROCEDURE bubble_sort(list)
    n ← length(list)
    FOR i ← 0 TO n-2
        swapped ← FALSE
        FOR j ← 0 TO n-2-i
            IF list[j] > list[j+1] THEN
                SWAP list[j], list[j+1]
                swapped ← TRUE
            ENDIF
        NEXT j
        IF swapped = FALSE THEN
            BREAK
        ENDIF
    NEXT i
END PROCEDURE

注意伪代码中使用了 swapped 标志来优化。在 CIE 考试中，你可能需要写出类似的伪代码或跟踪变量值。

5. Insertion Sort – Basic Idea | 插入排序 – 基本思想

Insertion sort builds the final sorted list one element at a time. It takes each element from the unsorted part and “inserts” it into its correct position within the already sorted part by shifting larger elements to the right. It works similarly to how you might sort playing cards in your hand.

插入排序一次一个元素地构建最终排序列表。它从未排序部分取出每个元素，通过将较大的元素向右移动，将它“插入”到已排序部分的正确位置。它的工作方式类似于你对手中的扑克牌进行排序。

6. Insertion Sort – Step-by-Step Example | 插入排序 – 逐步示例

Take the list [9, 5, 1, 4, 3]. Start from index 1 (value 5). Compare with 9, shift 9 right, insert 5 → [5, 9, 1, 4, 3]. Next, pick 1: compare with 9 and 5, shift both right, insert 1 → [1, 5, 9, 4, 3]. Pick 4: compare with 9 and 5 (shift them right), insert 4 → [1, 4, 5, 9, 3]. Finally, pick 3: shift 9,5,4 right, insert 3 → [1, 3, 4, 5, 9]. The list is sorted.

以列表 [9, 5, 1, 4, 3] 为例。从索引 1（值 5）开始。与 9 比较，将 9 右移，插入 5 → [5, 9, 1, 4, 3]。接下来，选取 1：与 9 和 5 比较，两者都右移，插入 1 → [1, 5, 9, 4, 3]。选取 4：与 9 和 5 比较（将它们右移），插入 4 → [1, 4, 5, 9, 3]。最后，选取 3：将 9,5,4 右移，插入 3 → [1, 3, 4, 5, 9]。列表已排序。

7. Insertion Sort – Algorithm and Pseudocode | 插入排序 – 算法与伪代码

Insertion sort is efficient for small or nearly sorted lists. It uses a single loop that picks the next element and then a while loop to shift elements larger than the key to the right until the correct spot is found. The worst-case time complexity is O(n²), but best-case (already sorted) is O(n).

插入排序对于小型或接近排序的列表效率很高。它使用一个循环来选取下一个元素，然后使用一个 while 循环将大于该键值的元素向右移动，直到找到正确的位置。最坏情况时间复杂度为 O(n²)，但最佳情况（已排序）是 O(n)。

PROCEDURE insertion_sort(list)
    n ← length(list)
    FOR i ← 1 TO n-1
        key ← list[i]
        j ← i - 1
        WHILE j ≥ 0 AND list[j] > key
            list[j+1] ← list[j]
            j ← j - 1
        ENDWHILE
        list[j+1] ← key
    NEXT i
END PROCEDURE

注意：key 存储当前要插入的值，while 循环将大于 key 的元素依次后移，最后将 key 插入空位。

8. Merge Sort – Basic Idea (Divide and Conquer) | 归并排序 – 基本思想（分治法）

Merge sort is a divide-and-conquer algorithm. It recursively splits the list into halves until each sublist contains only one element (which is trivially sorted). Then it repeatedly merges the sublists back together, comparing elements one by one to produce a new sorted list. This process guarantees O(n log n) time complexity.

归并排序是一种分治算法。它递归地将列表拆分为两半，直到每个子列表只包含一个元素（自然已排序）。然后它反复将这些子列表合并在一起，逐一比较元素以产生新的排序列表。这个过程保证了 O(n log n) 的时间复杂度。

9. Merge Sort – Step-by-Step Example | 归并排序 – 逐步示例

Sort [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] and [9],[82],[10]. Merge pairs: [38] and [27] → [27,38]; [43] and [3] → [3,43]; then merge these → [3,27,38,43]. For the right half: [9] and [82] → [9,82]; merge with [10] → [9,10,82]. Finally, merge the two sorted halves [3,27,38,43] and [9,10,82] to get the fully sorted list [3,9,10,27,38,43,82].

排序 [38, 27, 43, 3, 9, 82, 10]。拆分：[38,27,43,3] 和 [9,82,10]。继续拆分直到单个元素：[38],[27],[43],[3] 和 [9],[82],[10]。成对合并：[38] 和 [27] → [27,38]；[43] 和 [3] → [3,43]；然后合并这些 → [3,27,38,43]。对于右半部分：[9] 和 [82] → [9,82]；与 [10] 合并 → [9,10,82]。最后，合并两个已排序的半部分 [3,27,38,43] 和 [9,10,82] 得到完全排序的列表 [3,9,10,27,38,43,82]。

10. Merge Sort – Pseudocode and Complexity | 归并排序 – 伪代码与复杂度

Merge sort uses a helper function to merge two sorted arrays. The main function recursively splits the array and then merges. The time complexity is O(n log n) in all cases, which is more efficient than bubble and insertion sort for large datasets. However, it requires additional memory for the temporary arrays during merging (space complexity O(n)).

归并排序使用一个辅助函数来合并两个已排序的数组。主函数递归地拆分数组，然后合并。在所有情况下时间复杂度都是 O(n log n)，这对于大型数据集比冒泡排序和插入排序更高效。但是，它在合并期间需要额外内存用于临时数组（空间复杂度 O(n)）。

PROCEDURE merge_sort(list)
    IF length(list) ≤ 1 THEN RETURN list
    mid ← length(list) DIV 2
    leftHalf ← list[0..mid-1]
    rightHalf ← list[mid..end]
    leftSorted ← merge_sort(leftHalf)
    rightSorted ← merge_sort(rightHalf)
    RETURN merge(leftSorted, rightSorted)
END PROCEDURE

PROCEDURE merge(left, right)
    result ← empty list
    WHILE left NOT empty AND right NOT empty
        IF left[0] ≤ right[0] THEN
            APPEND left[0] to result
            REMOVE left[0] from left
        ELSE
            APPEND right[0] to result
            REMOVE right[0] from right
        ENDIF
    ENDWHILE
    APPEND remaining left to result
    APPEND remaining right to result
    RETURN result
END PROCEDURE

在 CIE GCSE 考试中，你可能需要理解合并过程并能追溯递归调用，但不需要写出完整的递归代码；不过，熟悉伪代码有助于理解。

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

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
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 implement and use constant extra memory, but they become slow on large lists. Merge sort is faster for large data but uses extra memory. Stability means elements with equal keys retain their original relative order after sorting.

冒泡排序和插入排序实现简单，使用常数额外内存，但在大列表上变慢。归并排序对于大数据更快，但使用额外内存。稳定性意味着具有相等键值的元素在排序后保持其原始相对顺序。

12. Exam Tips for Sorting Algorithms | 排序算法的考试技巧

In the CIE GCSE exam, you may be asked to trace an algorithm on a given dataset, complete a partially filled trace table, or identify which algorithm is being described. You should be able to write pseudocode for bubble sort and insertion sort, and explain the divide-and-conquer approach of merge sort. Always show your working neatly, use correct indentation, and remember to mention early termination optimisations where relevant.

在 CIE GCSE 考试中，你可能需要针对给定数据集跟踪算法、完成部分填充的跟踪表，或识别正在描述哪种算法。你应该能够写出冒泡排序和插入排序的伪代码，并解释归并排序的分治方法。始终整洁地展示你的过程，使用正确的缩进，并记得在相关时提及提前终止的优化。

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

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

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