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

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

Sorting is one of the most fundamental operations in computer science. Whether you are searching a database, organising a list of contacts, or preparing data for efficient processing, a well-chosen sorting algorithm can dramatically improve performance. For IB and AQA Computer Science students, mastering the three core sorting algorithms — bubble sort, insertion sort, and merge sort — is essential. This article provides a detailed, bilingual breakdown of each algorithm, covering their mechanics, pseudocode, worked examples, time complexities, stability, and practical use cases.

排序是计算机科学中最基础的操作之一。无论是搜索数据库、整理联系人列表，还是为高效处理准备数据，选择合适的排序算法都能显著提升性能。对于 IB 和 AQA 计算机科学的学生来说，掌握冒泡排序、插入排序和归并排序这三种核心算法至关重要。本文将用中英双语详细解析每种算法的机制、伪代码、示例、时间复杂度、稳定性以及实际应用场景。

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

Sorting is the process of arranging a collection of items in a specific order — typically ascending or descending — according to a key value. The items can be numbers, strings, or any objects that can be compared. Sorting makes searching faster, helps detect duplicates, and simplifies data presentation. In AQA specifications, three sorting algorithms are the main focus: bubble sort, insertion sort, and merge sort.

排序是将一组数据按特定顺序（通常是升序或降序）排列的过程，依据某个键值进行。数据项可以是数字、字符串或任何可比较的对象。排序能让查找更快、帮助检测重复项并简化数据呈现。在 AQA 考试大纲中，三种排序算法是重点：冒泡排序、插入排序和归并排序。

2. Why Sorting Matters | 排序为何重要

Many advanced algorithms, such as binary search, require sorted data to operate efficiently. Databases sort records to make retrieval faster; operating systems sort files by name or date; and e-commerce sites sort products by price or rating. Understanding how sorting works, and when to use each algorithm, is a key skill for any computer scientist.

许多高级算法（如二分查找）需要预先排序的数据才能高效运行。数据库通过对记录排序来加快检索；操作系统按名称或日期对文件排序；电商网站按价格或评分排列商品。理解排序的原理以及何时使用每种算法，是每一个计算机科学学生必须掌握的技能。

3. Bubble Sort | 冒泡排序

Bubble sort is a simple comparison-based algorithm. It 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. The name comes from the way smaller elements ‘bubble’ to the top of the list.

冒泡排序是一种简单的基于比较的算法。它反复遍历列表，比较相邻元素，如果顺序错误就交换它们。重复多次遍历，直到不需要任何交换，即列表已排序。其名称来源于较小的元素会像气泡一样“冒”到列表顶部。

4. Bubble Sort Algorithm and Example | 冒泡排序算法及示例

The algorithm works as follows: for each pass from the first element to the last, compare the current element with the next. If the current is greater than the next (for ascending order), swap them. After one full pass, the largest unsorted element settles at the end. Reduce the effective list size by one and repeat.

算法流程如下：从第一个元素到最后一个元素进行遍历，比较当前元素与下一个元素。如果当前元素大于下一个元素（对于升序），则交换。一趟结束后，最大的未排序元素会“沉”到末端。缩减有效列表长度，重复这一过程。

Pseudocode (Bubble Sort)

procedure bubbleSort(A : list of sortable items)
n = length(A)
repeat
  swapped = false
  for i = 0 to n-2
    if A[i] > A[i+1] then
      swap(A[i], A[i+1])
      swapped = true
  end for
  n = n – 1
until not swapped
end procedure

Example: Sort [5, 1, 4, 2, 8] ascending.
Pass 1: (5,1) swap → [1,5,4,2,8]; (5,4) swap → [1,4,5,2,8]; (5,2) swap → [1,4,2,5,8]; (5,8) no swap → [1,4,2,5,8].
Pass 2: (1,4) ok; (4,2) swap → [1,2,4,5,8]; remaining ok. Sorted in 2 passes.

示例：对 [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) 不交换 → [1,4,2,5,8]。
第二趟：(1,4) 正常；(4,2) 交换 → [1,2,4,5,8]；剩余正常。两趟后排序完成。

5. Insertion Sort | 插入排序

Insertion sort builds the final sorted list one item at a time. It works similarly to sorting playing cards in your hand: you pick a card from the unsorted pile and insert it into the correct position in the already sorted part. It is efficient for small datasets and partially sorted lists.

插入排序每次构建一个有序项，类似于整理手中的扑克牌：从无序牌堆中取出一张牌，将它插入到已排序部分的正确位置。对于小数据集和部分有序的列表，插入排序非常高效。

6. Insertion Sort Algorithm and Example | 插入排序算法及示例

Start from the second element (index 1) and compare it backwards with elements in the sorted portion (index 0 to i-1). Shift larger elements one position to the right until the correct spot for the current element is found, then insert it.

从第二个元素（索引 1）开始，将它向前与已排序部分（索引 0 到 i-1）的元素比较。将较大的元素向右移动一位，直到找到当前元素的正确位置，然后插入。

Pseudocode (Insertion Sort)

procedure insertionSort(A : list of sortable items)
for i = 1 to length(A)-1
  key = A[i]
  j = i – 1
  while j >= 0 and A[j] > key
    A[j+1] = A[j]
    j = j – 1
  end while
  A[j+1] = key
end for
end procedure

Example: Sort [5, 1, 4, 2, 8].
i=1: key=1, compare with 5, shift 5 right → [5,5,4,2,8], insert 1 → [1,5,4,2,8].
i=2: key=4, compare with 5, shift 5 → [1,5,5,2,8], compare with 1 (smaller), stop, insert 4 → [1,4,5,2,8].
i=3: key=2, shift 5,4 → [1,4,5,5,8], [1,4,4,5,8]; insert 2 → [1,2,4,5,8].
i=4: key=8, no shift needed. Final sorted list.

示例：对 [5, 1, 4, 2, 8] 排序。
i=1: key=1，与5比较，将5右移 → [5,5,4,2,8]，插入1 → [1,5,4,2,8]。
i=2: key=4，与5比较右移 → [1,5,5,2,8]，与1比较（更小）停止，插入4 → [1,4,5,2,8]。
i=3: key=2，移5、4 → [1,4,5,5,8], [1,4,4,5,8]；插入2 → [1,2,4,5,8]。
i=4: key=8，无需移动。最终有序列表。

7. Merge Sort | 归并排序

Merge sort is a divide-and-conquer algorithm. It recursively splits the list into two halves until each sublist contains a single element. Then it repeatedly merges the sublists to produce new sorted sublists until a fully sorted list remains. It is much more efficient on large datasets than bubble or insertion sort.

归并排序是一种分治算法。它递归地将列表分成两半，直到底层每个子列表只包含一个元素。然后不断合并子列表，产生新的有序子列表，最终得到一个完整有序的列表。对于大数据集，它比冒泡或插入排序高效得多。

8. Merge Sort Algorithm and Example | 归并排序算法及示例

The merge step is the core: take two sorted sublists and combine them into one sorted list by repeatedly taking the smaller of the two front elements. The recursive division continues until the base case of a single element is reached.

合并步骤是核心：取两个已排序子列表，通过反复取两者头部较小的元素，将它们合并成一个有序列表。递归划分持续进行，直到达到单个元素的基本情况。

Pseudocode (Merge Sort)

procedure mergeSort(A : list of sortable items)
if length(A) <= 1 then return A
mid = length(A) div 2
left = mergeSort(A[0..mid-1])
right = mergeSort(A[mid..end])
return merge(left, right)
end procedure

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]
while left is not empty append remaining left
while right is not empty append remaining right
return result

Example: Sort [5, 1, 4, 2, 8].
Split: [5,1,4] and [2,8] → [5] [1,4] ; [2] [8]
[1,4] splits → [1] [4] → merge → [1,4]; [5] and [1,4] merge → [1,4,5].
[2] [8] merge → [2,8]. Final merge [1,4,5] and [2,8] → [1,2,4,5,8].

示例：对 [5, 1, 4, 2, 8] 排序。
划分：[5,1,4] 和 [2,8] → [5] [1,4] ; [2] [8]
[1,4] 划分 → [1] [4] → 合并 → [1,4]；[5] 与 [1,4] 合并 → [1,4,5]。
[2] [8] 合并 → [2,8]。最终合并 [1,4,5] 和 [2,8] → [1,2,4,5,8]。

9. Comparing Sorting Algorithms: Time Complexity | 排序算法比较：时间复杂度

Time complexity describes how the running time grows with input size n. Using Big O notation, we can compare worst-case, best-case, and average-case scenarios. Understanding these helps you decide which algorithm to use for a given problem and dataset size.

时间复杂度描述了运行时间随输入规模 n 如何增长。使用大 O 表示法，我们可以比较最坏情况、最好情况和平均情况。理解这些有助于针对不同问题和数据集大小选择合适的算法。

Algorithm	Best Case	Average Case	Worst Case	Space Complexity
Bubble Sort	O(n)	O(n²)	O(n²)	O(1)
Insertion Sort	O(n)	O(n²)	O(n²)	O(1)
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)

Bubble and insertion sorts achieve O(n) best-case when the list is already sorted (or nearly sorted) because only one pass or minimal shifting is needed. Merge sort’s best case is also O(n log n) because it always divides and merges regardless of order.

当列表已经（或接近）有序时，冒泡和插入排序能达到 O(n) 的较好情况，因为只需一趟遍历或很少的移动。归并排序不论顺序如何都要进行划分与合并，因此最好情况也保持 O(n log n)。

10. Stability and In-Place Sorting | 稳定性与原地排序

A sorting algorithm is stable if it preserves the relative order of equal elements. For example, if two records have the same key, they appear in the sorted output in the same order as in the input. Stability matters when sorting by multiple attributes (e.g., first by name, then by grade). Bubble sort, insertion sort, and merge sort are all stable. Quick sort (not on the AQA list) is typically not stable without modification.

如果排序算法能保持相等元素的相对顺序，它就被称为稳定的。例如，两个记录具有相同的键值，它们在排序输出中的顺序与输入中一致。当需要按多个属性排序时（如先按姓名再按成绩），稳定性就很重要。冒泡排序、插入排序和归并排序都是稳定的。快速排序（不在 AQA 列表中）通常不经过修改是不稳定的。

An in-place algorithm uses a constant amount of extra memory (O(1) space). Bubble and insertion sorts are in-place; merge sort is not in-place because it requires O(n) extra space for the merging process. Understanding these traits helps predict memory usage.

原地算法只使用常数大小的额外内存（O(1) 空间）。冒泡和插入排序是原地的；归并排序不是原地的，因为在合并过程中需要 O(n) 的额外空间。理解这些特性有助于预测内存使用情况。

11. Choosing the Right Sort | 选择合适的排序算法

For small lists (n < 50), insertion sort is often the fastest due to low overhead, and it is stable and in-place. Bubble sort is rarely used in practice because of its poor average performance, but it is easy to understand and implement. Merge sort is the go-to choice for large datasets or when stable sorting is required, despite its extra memory cost. Many programming languages implement hybrid sorting (e.g., Timsort) that combines insertion and merge sort concepts for real-world efficiency.

对于小列表（n < 50），插入排序通常最快，因为其开销低，而且稳定、原地。冒泡排序在实际中很少使用，因为平均性能差，但它易于理解和实现。归并排序是大数据集或需要稳定排序时的首选，尽管它需要额外内存。许多编程语言实现了混合排序（如 Timsort），结合了插入排序和归并排序的思想，以达到实际应用中的高效。

In exam questions, you may be asked to trace an algorithm on a given list, identify which algorithm was used based on a trace, or discuss performance trade-offs. Always know the pseudocode steps and be able to simulate them manually.

在考试题中，可能会要求你在给定列表上跟踪算法执行过程，根据跟踪记录识别使用了哪种算法，或讨论性能权衡。务必熟悉伪代码步骤，并能手动模拟。

12. Key Takeaways | 小结

Mastering sorting algorithms gives you a solid foundation for analysing algorithm efficiency and thinking recursively. Remember: bubble sort uses repeated neighbour swaps; insertion sort builds a sorted portion by shifting elements; merge sort splits and conquers. Learn their time complexities, stability, and space requirements. Practice tracing them with pen and paper—this is the most effective way to prepare for IB and AQA assessments.

掌握排序算法为你分析算法效率和递归思维奠定了坚实基础。记住：冒泡排序使用反复的相邻交换；插入排序通过移动元素构建有序部分；归并排序采用分治策略。牢记它们的时间复杂度、稳定性和空间需求。用纸笔练习跟踪算法执行——这是备考 IB 和 AQA 考试最有效的方式。

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

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

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