Sorting Algorithms | 排序算法考点精讲

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

In GCSE CCEA Computer Science, sorting is a fundamental concept that underpins efficient data handling. You must understand how bubble sort, insertion sort, and merge sort work, be able to trace their execution on a given list, and compare their performance in terms of time complexity and number of comparisons or swaps. This article covers all essential points, from step‑by‑step algorithms to exam‑style analysis, with paired English and Chinese explanations.

在 GCSE CCEA 计算机科学课程中，排序是支撑高效数据管理的基础概念。你需要理解冒泡排序、插入排序和归并排序的工作原理，能够对给定的列表追踪执行过程，并从时间复杂度、比较次数和交换次数等角度比较它们的性能。本文涵盖从算法步骤到考试风格分析的所有核心考点，并配有中英对照讲解。

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

Sorting means arranging a list of items into a defined order – typically ascending (smallest to largest) or descending (largest to smallest). The items can be numbers, strings, or any data that can be compared.

排序是指将一组数据按照规定的顺序排列——通常是升序（从小到大）或降序（从大到小）。这些数据项可以是数字、字符串或任何可以进行比较的数据。

Sorting algorithms are studied because they illustrate different approaches to problem‑solving, and their efficiency directly affects the performance of larger programs such as search routines and database operations.

之所以学习排序算法，是因为它们展示了不同的问题解决方法，而它们的效率直接影响大型程序（如搜索例程和数据库操作）的性能。

In the CCEA specification, the three required sorting methods are Bubble Sort, Insertion Sort, and Merge Sort.

在 CCEA 考试大纲中，要求掌握的三种排序方法是冒泡排序、插入排序和归并排序。

2. Bubble Sort Explained | 冒泡排序详解

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.

冒泡排序的工作原理是反复遍历列表，比较相邻元素，如果顺序错误就交换它们。重复遍历列表，直到不再需要任何交换，这表明列表已经有序。

Algorithm in words: Start at the beginning of the list. Compare the first two elements. If the first is greater than the second (for ascending order), swap them. Move to the next pair (second and third), compare, and swap if needed. Continue to the end of the list. This is one pass. After each pass, the largest unsorted element ‘bubbles up’ to its correct position at the end. Repeat the process for the remaining unsorted part (ignoring the last sorted element) until no swaps occur in a complete pass.

算法描述：从列表的开头开始。比较前两个元素。如果第一个大于第二个（对于升序），则交换它们。移到下一对（第二个和第三个），比较，并在需要时交换。继续到列表末尾。这是一趟扫描。每趟扫描后，最大的未排序元素会“冒泡”到末尾的正确位置。对其余未排序部分（忽略最后一个已排序元素）重复该过程，直到一整趟扫描中没有发生任何交换。

Example trace on list [5, 3, 8, 1]:

对列表 [5, 3, 8, 1] 的追踪示例：

Pass 1: (5,3) → swap → [3,5,8,1]; (5,8) → no swap; (8,1) → swap → [3,5,1,8]. End of pass 1, largest 8 is in place.

第 1 趟：(5,3) → 交换 → [3,5,8,1]；(5,8) → 不交换；(8,1) → 交换 → [3,5,1,8]。第 1 趟结束，最大值 8 就位。
Pass 2: Compare [3,5,1] ignoring 8: (3,5) no swap; (5,1) swap → [3,1,5,8]. End of pass 2, 5 is in place.

第 2 趟：比较 [3,5,1]（忽略 8）：(3,5) 不交换；(5,1) 交换 → [3,1,5,8]。第 2 趟结束，5 就位。
Pass 3: Compare [3,1] ignoring 5,8: (3,1) swap → [1,3,5,8]. Sorted.

第 3 趟：比较 [3,1]（忽略 5,8）：(3,1) 交换 → [1,3,5,8]。已排序。

3. Bubble Sort Performance | 冒泡排序的性能

The worst‑case and average time complexity of bubble sort is O(n²), where n is the number of items. This is because in the worst case (reverse‑sorted list) every possible comparison and swap is performed: about n(n−1)/₂ comparisons.

冒泡排序的最坏情况和平均时间复杂度是 O(n²)，其中 n 是数据项的数量。这是因为在最坏情况下（列表反向有序），会执行所有可能的比较和交换：大约 n(n−1)/₂ 次比较。

The best‑case time complexity is O(n) when the list is already sorted. Only one pass is needed, with no swaps, but the algorithm still checks every adjacent pair to confirm it is sorted (n−1 comparisons).

当列表已经有序时，最好情况的时间复杂度是 O(n)。只需一趟扫描，没有交换，但算法仍会检查每一对相邻元素以确认有序（n−1 次比较）。

Total number of swaps in the worst case is also O(n²). Bubble sort is stable (items with equal keys remain in their original relative order) and works ‘in‑place’ – meaning it requires only a constant amount of extra memory space (O(1)).

最坏情况下的总交换次数也是 O(n²)。冒泡排序是稳定的（具有相同键值的项的原始相对顺序保持不变），并且是“原地”工作——意味着它只需要常数级别的额外内存空间 (O(1))。

Property	Bubble Sort
Worst-case time	O(n²)
Best-case time	O(n)
Average time	O(n²)
Stable?	Yes
In‑place?	Yes

Exam tip: You should be able to count the number of comparisons and swaps for a given list length in the worst, best, and average cases.

考试提示：你应该能够针对给定的列表长度，计算最坏、最好和平均情况下的比较次数和交换次数。

4. Insertion Sort Explained | 插入排序详解

Insertion sort builds the final sorted list one item at a time. It picks the next element from the unsorted part and inserts it into its correct position within the already sorted part, shifting larger elements to the right to make room.

插入排序每次构建一项最终有序列表。它从未排序部分取出下一个元素，并将其插入到已排序部分的正确位置，将较大的元素向右移动以腾出空间。

Algorithm: Start with the second element (index 1) as the ‘current’ item. Compare it with elements to its left in the sorted part. If the current item is smaller, shift the compared element one position to the right. Repeat until the correct position is found, then place the current item there. Move to the next unsorted element and repeat until the whole list is processed.

算法：从第二个元素（索引 1）开始作为“当前”项。将其与左侧已排序部分的元素进行比较。如果当前项较小，则将所比较的元素向右移动一个位置。重复该过程直到找到正确的位置，然后将当前项插入。移到下一个未排序元素，重复直至整个列表处理完毕。

Example on [5, 3, 8, 1]:

示例 [5, 3, 8, 1]：

Start: sorted part = [5]; unsorted = [3,8,1]. Take 3, compare with 5: 3 < 5, shift 5 right → list becomes [ ,5,8,1]; insert 3 at position 0 → [3,5,8,1].

开始：已排序部分 = [5]；未排序 = [3,8,1]。取 3，与 5 比较：3 < 5，将 5 右移 → 列表变为 [ ,5,8,1]；在位置 0 插入 3 → [3,5,8,1]。
Next: sorted part = [3,5]; unsorted = [8,1]. Take 8, compare with 5: 8 > 5, no shift, insert after 5 → [3,5,8,1].

下一步：已排序部分 = [3,5]；未排序 = [8,1]。取 8，与 5 比较：8 > 5，不移位，插入到 5 后面 → [3,5,8,1]。
Next: sorted part = [3,5,8]; unsorted = [1]. Take 1, compare with 8 (shift 8 right), with 5 (shift 5 right), with 3 (shift 3 right), insert 1 at start → [1,3,5,8].

下一步：已排序部分 = [3,5,8]；未排序 = [1]。取 1，与 8 比较（8 右移），与 5 比较（5 右移），与 3 比较（3 右移），在开头插入 1 → [1,3,5,8]。

Insertion sort behaves like sorting playing cards in your hand: you pick up a new card and insert it into the correct position among the cards you already hold.

插入排序就像整理手中的扑克牌：你拿起一张新牌，将其插入到手中已有牌的正确位置。

5. Insertion Sort Performance | 插入排序的性能

Insertion sort, like bubble sort, has a worst‑case and average time complexity of O(n²). The worst case occurs when the list is in reverse order, requiring shifting all previously sorted elements for each new insert.

与冒泡排序一样，插入排序的最坏情况和平均时间复杂度也是 O(n²)。最坏情况出现在列表反向有序时，每次插入都几乎需要移动所有已排序的元素。

However, the best case (list already sorted) gives O(n) time because the inner loop simply checks the immediate left neighbour and finds the item is already in the correct place, so no shifts occur. Nevertheless, comparisons are still made for each element (n−1 comparisons).

然而，最好情况（列表已有序）的时间复杂度为 O(n)，因为内层循环只需检查左侧紧邻的元素，就发现该项目已在正确位置，因此不发生任何移位。但仍然会对每个元素进行比较（n−1 次）。

Insertion sort is stable and in‑place (O(1) extra memory). It often performs fewer comparisons and swaps than bubble sort in practice, especially on nearly sorted data. It is used in hybrid sorting algorithms like Timsort for small sublists.

插入排序是稳定的且原地工作（O(1) 的额外内存）。在实践中，特别是对于接近有序的数据，它通常比冒泡排序执行更少的比较和交换。它被用于像 Timsort 这样的混合排序算法中，用于处理小型子列表。

Property	Insertion Sort
Worst-case time	O(n²)
Best-case time	O(n)
Average time	O(n²)
Stable?	Yes
In‑place?	Yes

Comparison between bubble sort and insertion sort often appears in exam questions; you may be asked which algorithm would finish faster on a nearly sorted list (insertion sort).

冒泡排序和插入排序的比较经常出现在考题中；你可能会被问到在接近有序的列表上哪种算法完成得更快（插入排序）。

6. Merge Sort Explained | 归并排序详解

Merge sort is a divide‑and‑conquer algorithm. It splits the list into two halves recursively until each sublist contains a single element (which is trivially sorted). Then it repeatedly merges the sublists back together, comparing the smallest elements of each sublist to produce a new sorted list.

归并排序是一种分治算法。它递归地将列表分成两半，直到每个子列表只包含一个元素（单个元素自然是已排序的）。然后它反复合并这些子列表，比较每个子列表的最小元素，生成新的有序列表。

High‑level algorithm: If the list has more than one element, find the middle index. Recursively apply merge sort to the left half and to the right half. Merge the two sorted halves: compare the first elements of each half, take the smaller one, and move it to the merged list. Repeat until one half is exhausted, then copy any remaining elements.

高层算法：如果列表有多个元素，找到中间索引。对左半部分递归应用归并排序，对右半部分也递归应用。合并两个已排序的子列表：比较每一半的第一个元素，取出较小的那个，将其移到合并后的列表中。重复直到某一半为空，然后复制剩余的所有元素。

Example on [5, 3, 8, 1]: Split into [5,3] and [8,1].

示例 [5, 3, 8, 1]：分成 [5,3] 和 [8,1]。

Left half [5,3]: split into [5] and [3]. Merge: compare 5 and 3 → take 3, then 5 → [3,5].

左半 [5,3]：分成 [5] 和 [3]。合并：比较 5 和 3 → 取 3，然后 5 → [3,5]。
Right half [8,1]: split into [8] and [1]. Merge: take 1, then 8 → [1,8].

右半 [8,1]：分成 [8] 和 [1]。合并：取 1，然后 8 → [1,8]。
Final merge of [3,5] and [1,8]: compare 3 and 1 → take 1; compare 3 and 8 → take 3; compare 5 and 8 → take 5; take 8. Result [1,3,5,8].

最终合并 [3,5] 和 [1,8]：比较 3 和 1 → 取 1；比较 3 和 8 → 取 3；比较 5 和 8 → 取 5；取 8。结果 [1,3,5,8]。

Merge sort is fundamentally different: it requires additional memory proportional to the size of the list for the temporary arrays used during merging.

归并排序有本质的不同：它在合并过程中需要与列表大小成比例的额外内存来存储临时数组。

7. Merge Sort Performance | 归并排序的性能

Merge sort guarantees O(n log n) time complexity in all cases – worst, average, and best – because the list is divided log₂(n) times and each level of merging processes all n elements. This makes it much faster than bubble or insertion sort for large lists.

归并排序在所有情况下（最坏、平均和最好）都保证 O(n log n) 时间复杂度，因为列表被分割 log₂(n) 次，而每一层合并都处理全部 n 个元素。这使得它对于大型列表比冒泡排序或插入排序快得多。

However, its space complexity is O(n) because it needs extra storage for the left and right temporary sublists during merging. Merge sort is stable (can be implemented to preserve order of equal elements) but is not in‑place due to the extra memory required.

然而，它的空间复杂度是 O(n)，因为在合并时需要为左右临时子列表提供额外存储空间。归并排序是稳定的（可以通过实现保持相等元素的顺序），但由于需要额外内存，它不是原地算法。

Comparison count in merge sort per merge step is roughly the total number of items being merged minus the number of times one list is exhausted before the other. Overall, it performs fewer comparisons than bubble and insertion sorts on random data.

在归并排序中，每次合并步骤的比较次数大约等于正在合并的元素总数减去某列表提前耗尽的情况次数。总体而言，对于随机数据，它比冒泡排序和插入排序执行更少的比较次数。

Property	Merge Sort
Worst-case time	O(n log n)
Best-case time	O(n log n)
Average time	O(n log n)
Stable?	Yes
In‑place?	No (needs O(n) extra space)

8. Tracing and Comparing Algorithms | 算法追踪与比较

CCEA exam questions often ask you to trace the steps of a sort on a small list. You must show the list after each pass (bubble), after each insertion (insertion), or the splitting/merging tree (merge). Accuracy is vital: carefully label each stage and indicate when elements are in their final positions.

CCEA 考试题目经常要求你追踪一个小列表上的排序步骤。你必须展示每趟扫描后（冒泡）、每次插入后（插入）的状态，或者分裂/合并树（归并）。准确性至关重要：仔细标注每个阶段，并指出元素何时到达最终位置。

You should also be able to compare algorithms by stating which is faster for large datasets (merge sort), which uses less memory (bubble and insertion – in‑place), and which is simplest to code (bubble). GCSE marks are often awarded for justified choices.

你还应该能够比较算法，说出哪种算法对大数据集更快（归并排序），哪种使用更少内存（冒泡和插入——原地），以及哪种编码最简单（冒泡）。GCSE 评分通常奖励有理由支持的选择。

Typical comparison statements:

典型的比较陈述：

Bubble sort is easy to understand but inefficient for large n due to O(n²) running time.

冒泡排序易于理解，但由于 O(n²) 的运行时间，对于较大的 n 效率低下。
Insertion sort is simple and performs well on small or nearly sorted lists; it is often used as part of more complex algorithms.

插入排序简单，在小型或接近有序的列表上表现良好；它常被用作更复杂算法的一部分。
Merge sort is much faster for large lists but requires additional memory, which may be a constraint on memory‑limited devices.

归并排序对于大型列表快得多，但需要额外的内存，这在内存受限设备上可能是一种约束。

9. Standard Exam Questions | 常见考试题型

Question style 1: ‘Show how bubble sort would sort the list [6, 2, 9, 4].’ You must draw or list each pass until no swaps occur. Remember, after pass 1, the largest item is at the end; after pass 2, the next largest is in place, etc.

题型 1：“展示冒泡排序如何对列表 [6, 2, 9, 4] 进行排序。”你必须画出或列出每趟扫描的结果，直到不再发生交换。记住，第 1 趟后，最大项在末尾；第 2 趟后，次大项就位，依此类推。

Question style 2: ‘Given a nearly sorted list, which algorithm would you choose and why?’ The accepted answer is usually insertion sort because its best case is O(n) and it minimises shifts when data is almost sorted.

题型 2：“给定一个接近有序的列表，你会选择哪种算法，为什么？”通常接受的答案是插入排序，因为它的最好情况是 O(n)，并且在数据几乎有序时最小化移位。

Question style 3: ‘Complete the merge sort tree for [8, 3, 5, 2, 7, 4]’ – you need to show splitting until single elements, then the merging steps back up with values.

题型 3：“完成列表 [8, 3, 5, 2, 7, 4] 的归并排序树”——你需要展示分裂到单元素，然后向上合并的步骤并标注数值。

Question style 4: ‘State the time complexity of merge sort and explain why it is more efficient than bubble sort for large n.’ Answer: Merge sort is O(n log n), while bubble sort is O(n²). For large n, n log n grows much slower than n², so merge sort performs fewer operations.

题型 4：“说出归并排序的时间复杂度，并解释为什么对于大的 n 它比冒泡排序更高效。”答案：归并排序是 O(n log n)，而冒泡排序是 O(n²)。对于大的 n，n log n 的增长远慢于 n²，因此归并排序执行更少的操作。

10. Practical Implementation Considerations | 实际实现注意事项

In your programming practice, you might implement these algorithms in Python. Bubble sort can be coded with a nested loop and a flag ‘swapped’ to detect early completion. Insertion sort uses a ‘key’ variable and a while loop to shift elements. Merge sort is typically written recursively: a base case when length ≤ 1, then merge( mergeSort(left), mergeSort(right) ).

在你的编程实践中，你可能用 Python 实现这些算法。冒泡排序可以用嵌套循环和一个标志 “swapped” 来检测提前完成。插入排序使用一个 “key” 变量和一个 while 循环来移动元素。归并排序通常以递归方式编写：基本情况是长度 ≤ 1，然后是 merge( mergeSort(left), mergeSort(right) )。

When tracing recursive merge sort, the call stack grows log₂(n) deep. This is acceptable for moderate sizes, but very deep recursion could cause stack overflow in some languages – though not a concern at GCSE level.

当追踪递归归并排序时，调用栈深度为 log₂(n)。对于中等规模可以接受，但在某些语言中，非常深的递归可能导致栈溢出——不过在 GCSE 阶段无需担心。

Understanding the difference between comparison‑based sorts and non‑comparison sorts is not required by CCEA, but you should know that all three studied algorithms are comparison‑based: they determine order by comparing elements pairwise.

CCEA 不要求理解基于比较的排序和非比较排序之间的区别，但你应该知道所学的三种算法都是基于比较的：它们通过成对比较元素来决定顺序。

11. Summary and Key Points to Remember | 总结与记忆要点

Bubble sort: O(n²) average/worst, O(n) best; in‑place, stable; uses repeated adjacent swaps.

冒泡排序：平均/最坏 O(n²)，最好 O(n)；原地，稳定；使用重复的相邻交换。
Insertion sort: O(n²) average/worst, O(n) best; in‑place, stable; builds sorted list by inserting each element into the correct position.

插入排序：平均/最坏 O(n²)，最好 O(n)；原地，稳定；通过将每个元素插入正确位置来构建有序列表。
Merge sort: O(n log n) in all cases; not in‑place (O(n) extra space), stable; uses divide‑and‑conquer strategy.

归并排序：所有情况 O(n log n)；非原地（O(n) 额外空间），稳定；使用分治策略。
Always talk about stability, space, and time complexity when comparing; these are the key marking points.

比较时始终提及稳定性、空间和时间复杂度；这些是关键得分点。
Trace carefully: show every pass for bubble, every insertion for insertion, the recursive splitting and merging for merge sort.

仔细追踪：冒泡展示每趟，插入展示每次插入，归并展示递归分裂和合并。

The efficiency formulas often involve sums: comparisons in bubble sort (worst) = n(n−1)/₂ ; comparisons in insertion sort (worst) ≈ n(n−1)/₂ ; comparisons in merge sort ≈ n log₂ n (roughly). You may be asked to calculate these for small n, e.g. n=6.

效率公式常涉及求和：冒泡排序比较次数（最坏）= n(n−1)/₂ ；插入排序比较次数（最坏）≈ n(n−1)/₂ ；归并排序比较次数 ≈ n log₂ n（大约）。你可能会被要求针对小的 n 计算这些值，例如 n=6。

12. Final Exam Advice | 考前建议

When answering questions, always relate the algorithm’s behaviour to the given data. Use the correct terminology: ‘pass’, ‘swap’, ‘shift’, ‘merge’, ‘recursive call’. Show your working clearly – marks are given for intermediate steps even if the final list is correct. If space is provided for a trace table, fill it in methodically.

答题时，始终将算法的行为与给定数据结合起来。使用正确的术语：“趟”、“交换”、“移位”、“合并”、“递归调用”。清晰地展示你的推导过程——即使最终列表正确，中间步骤也会给分。如果提供了追踪表格，请有条理地填写。

Finally, remember that sorting algorithms are a classic exam topic because they test algorithmic thinking, pattern recognition, and computational efficiency – core principles of computer science.

最后，请记住排序算法是一个经典的考试主题，因为它们测试算法思维、模式识别和计算效率——这些是计算机科学的核心原则。

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

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

Sorting Algorithms | 排序算法考点精讲