Sorting Algorithms for AQA A-Level Computer Science | AQA A-Level 计算机排序算法考点精讲

📚 Sorting Algorithms for AQA A-Level Computer Science | AQA A-Level 计算机排序算法考点精讲

Sorting is a fundamental concept in computer science, and the AQA A-Level specification requires you to understand, implement, and compare key sorting algorithms. This article covers bubble sort, insertion sort, merge sort, and quicksort, along with their time and space complexities, stability, and suitability for different situations.

排序是计算机科学中的一个基本概念，AQA A-Level 大纲要求你理解、实现并比较关键的排序算法。本文涵盖了冒泡排序、插入排序、归并排序和快速排序，以及它们的时间与空间复杂度、稳定性和在不同场景下的适用性。

1. Overview of Sorting Algorithms | 排序算法概述

Sorting algorithms arrange items in a particular order, typically numerical or lexicographical. They are classified by whether they are comparison-based, their time complexity, whether they are in-place, and whether they are stable. A stable sort preserves the relative order of records with equal keys; an in-place sort uses only a constant amount of extra memory (O(1) space) or a logarithmic amount for recursion while not duplicating the input array.

排序算法将项目按特定顺序排列，通常是数值或字典序。它们根据是否基于比较、时间复杂度、是否原地排序以及是否稳定来分类。稳定排序保持具有相等键的记录的相对顺序；原地排序只使用常量额外内存（O(1)空间）或递归所需的对数级空间，而不复制原始输入数组。

Understanding these properties is essential for answering exam questions that ask you to select the most appropriate algorithm for a given scenario. For instance, if memory is severely limited, an in-place O(1) algorithm like insertion sort might be preferred over merge sort, even if the latter is faster in big O terms.

理解这些属性对于回答考试中要求你为特定场景选择最合适算法的问题至关重要。例如，如果内存严重受限，像插入排序这样原地 O(1) 的算法可能比归并排序更受青睐，尽管后者在大 O 意义上更快。

2. Bubble Sort | 冒泡排序

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, indicating that the list is sorted. It is named because smaller elements ‘bubble’ to the top (beginning) of the list.

冒泡排序反复遍历列表，比较相邻元素，如果顺序错误则交换它们。这个过程重复进行，直到不需要交换为止，表明列表已排序。它的名称源于较小的元素会“冒泡”到列表的顶端（开头）。

The basic version of bubble sort always performs n-1 passes, resulting in a fixed O(n²) time. However, an optimized version can stop early if a pass completes without any swaps, giving a best-case time of O(n) when the input is already sorted. The algorithm is stable because it only swaps adjacent items when strictly greater, preserving the order of equal elements. It is also in-place, using O(1) extra space.

基础版的冒泡排序总是执行 n-1 趟，导致固定的 O(n²) 时间。然而，优化版本可以在某趟没有发生任何交换时提前停止，从而在输入已排序时获得 O(n) 的最佳情况时间。该算法是稳定的，因为它仅在严格大于时才交换相邻项，从而保持了相等元素的顺序。它也是原地排序，使用 O(1) 额外空间。

Pseudocode for the optimized bubble sort:
REPEAT
  swapped ← false
  FOR i ← 0 TO n-2
    IF arr[i] > arr[i+1] THEN
      SWAP arr[i], arr[i+1]
      swapped ← true
    ENDIF
  NEXT i
UNTIL NOT swapped

优化冒泡排序的伪代码：
REPEAT
  swapped ← false
  FOR i ← 0 TO n-2
    IF arr[i] > arr[i+1] THEN
      SWAP arr[i], arr[i+1]
      swapped ← true
    ENDIF
  NEXT i
UNTIL NOT swapped

3. Insertion Sort | 插入排序

Insertion sort builds the final sorted array one item at a time. It takes each element from the unsorted part and inserts it into the correct position within the sorted part, shifting larger elements to the right as needed. This process resembles sorting playing cards in your hand.

插入排序每次构建一个最终排序数组。它从无序部分取出每个元素，并将其插入到有序部分中的正确位置，必要时将较大元素向右移动。这个过程类似于整理手中的扑克牌。

The time complexity is O(n²) in the worst and average cases, but it can run in O(n) time when the input is already or nearly sorted, making it an adaptive sort. Space complexity is O(1), and it is both in-place and stable. Because of its low overhead, insertion sort is often used as the base case in more advanced algorithms such as Timsort.

时间复杂度在最坏和平均情况下为 O(n²)，但当输入已排序或近乎排序时，它可以以 O(n) 时间运行，这使它成为一种自适应排序。空间复杂度为 O(1)，它既是原地的也是稳定的。由于其低开销，插入排序经常被用作更高级算法（如 Timsort）的基础情况。

Algorithm steps summarised:
1. For each index j from 1 to n-1:
2. key ← arr[j]
3. i ← j-1
4. WHILE i ≥ 0 AND arr[i] > key
    arr[i+1] ← arr[i]
    i ← i-1
5. arr[i+1] ← key

算法步骤总结：
1. 对于从 1 到 n-1 的每个索引 j：
2. key ← arr[j]
3. i ← j-1
4. WHILE i ≥ 0 AND arr[i] > key
    arr[i+1] ← arr[i]
    i ← i-1
5. arr[i+1] ← key

In the worst-case reverse-sorted input, insertion sort makes approximately n²/2 comparisons and shifts. In the best case, it makes only n-1 comparisons with no shifts. This behaviour contrasts with bubble sort, where the optimized version also achieves O(n) best case but often with more swaps.

在最坏的逆序输入情况下，插入排序大约进行 n²/2 次比较和移位。在最佳情况下，它只进行 n-1 次比较而没有移位。这种行为与冒泡排序不同，后者优化版本也能实现 O(n) 最佳情况，但通常伴随更多的交换。

4. Merge Sort | 归并排序

Merge sort is a classic divide-and-conquer algorithm. It recursively divides the list into two halves until

Published by TutorHao | A-Level Computer Science Revision Series | aleveler.com

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