A-Level Computer Science: Sorting Algorithms - Essential Revision | A-Level 计算机：排序考点精讲

📚 A-Level Computer Science: Sorting Algorithms – Essential Revision | A-Level 计算机：排序考点精讲

Sorting algorithms form a cornerstone of the A-Level Computer Science syllabus. They test your ability to understand algorithmic thinking, analyse efficiency, and compare trade‑offs between different approaches. In this article, we break down the most important sorting methods you need to master, covering their mechanics, pseudocode, time complexities, and exam‑style considerations.

排序算法是 A-Level 计算机科学课程的重要基石。它们考察你对算法思维的理解、对效率的分析以及比较不同方法之间权衡的能力。本文将为你详细解析必须掌握的关键排序方法，涵盖其工作机制、伪代码、时间复杂度以及考试中需要关注的要点。

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

Sorting is the process of arranging elements in a list or array into a particular order – most commonly ascending or descending numerical order, or lexicographical order for strings. Sorting is fundamental because many other algorithms, such as binary search, rely on sorted data. In exams, you will be expected to trace, write pseudocode for, and evaluate the performance of several standard algorithms.

排序是将列表或数组中的元素按特定顺序进行排列的过程——最常见的是按数值升序或降序，或按字符串的字典序。排序之所以基础，是因为许多其他算法（如二分查找）依赖已排序的数据。在考试中，你需要能够跟踪执行、编写伪代码，并评估几种标准算法的性能。

A-Level specifications typically require in‑depth knowledge of bubble sort, insertion sort, selection sort, merge sort, and quick sort. You must understand their worst‑case and best‑case time complexities, space requirements, stability, and adaptivity.

A-Level 考试大纲通常要求深入掌握冒泡排序、插入排序、选择排序、归并排序和快速排序。你必须理解它们的最坏情况和最好情况时间复杂度、空间需求、稳定性以及适应性。

2. Bubble Sort | 冒泡排序

Bubble sort repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. After each full pass, the largest unsorted element ‘bubbles up’ to its correct position at the end of the list. The process continues until no swaps are needed, indicating that the list is sorted.

冒泡排序重复遍历列表，比较相邻元素，如果顺序错误则交换它们。每完成一次完整遍历，最大的未排序元素就会“冒泡”到列表末尾的正确位置。此过程持续进行，直到某次遍历中不需要任何交换，表明列表已排序。

Pseudocode for bubble sort (ascending):

冒泡排序伪代码（升序）：

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] and A[i+1]
                swapped = true
            end if
        end for
        n = n - 1
    until not swapped
end procedure

Time complexity: worst‑case O(n²), best‑case O(n) when the list is already sorted (if an optimised version with early exit is used). Space complexity: O(1) as it sorts in place. Bubble sort is stable: equal elements retain their relative order. It is adaptive because it can terminate early when no swaps occur.

时间复杂度：最坏情况 O(n²)，最好情况 O(n)（当列表已经有序时，使用带提前终止的优化版本）。空间复杂度：O(1)，因为它是原地排序。冒泡排序是稳定的：相等元素保持其相对顺序。它是适应性的，因为在没有发生交换时可以提前终止。

3. Insertion Sort | 插入排序

Insertion sort builds the sorted list one element at a time by repeatedly taking the next unsorted element and inserting it into its correct position within the already sorted portion. It is analogous to sorting playing cards in your hand: you pick up a card and place it in the right place among the cards you already hold.

插入排序通过逐个取下一个未排序元素并将其插入到已排序部分的正确位置来逐步构建有序列表。这类似于你整理手中的扑克牌：你拿起一张牌并将其放入手中已有牌的正确位置。

Pseudocode for insertion sort:

插入排序伪代码：

procedure insertionSort(A)
    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

Worst‑case time complexity O(n²) when the input is in reverse order; best‑case O(n) when the list is already sorted. It is an in‑place algorithm (O(1) extra space). Insertion sort is stable and adaptive, performing efficiently on nearly sorted data.

最坏情况时间复杂度为 O(n²)，发生在输入为逆序时；最好情况为 O(n)，当列表已经有序时。它是一种原地算法（O(1) 额外空间）。插入排序是稳定的且具有适应性，在数据接近有序时表现高效。

4. Selection Sort | 选择排序

Selection sort divides the input list into a sorted and an unsorted region. It repeatedly selects the smallest (or largest) element from the unsorted region and swaps it with the leftmost unsorted element, moving the boundary one position to the right. Unlike bubble sort, selection sort always makes exactly n–1 swaps.

选择排序将输入列表分为已排序区和未排序区。它反复从未排序区中选择最小（或最大）元素，并将其与最左边的未排序元素交换，然后将边界向右移动一位。与冒泡排序不同，选择排序总是恰好进行 n–1 次交换。

Pseudocode:

伪代码：

procedure selectionSort(A)
    n = length(A)
    for i = 0 to n-2
        minIndex = i
        for j = i+1 to n-1
            if A[j] < A[minIndex] then
                minIndex = j
            end if
        end for
        if minIndex != i then
            swap A[i] and A[minIndex]
        end if
    end for
end procedure

Time complexity is O(n²) in all cases – best, average, and worst – because the nested loops always run fully. It requires O(1) additional memory. Selection sort is not stable (the swap can change the relative order of equal items). It is not adaptive: its runtime does not improve for partially sorted data.

在所有情况下（最好、平均、最坏），时间复杂度均为 O(n²)，因为嵌套循环总是完整执行。它需要 O(1) 额外内存。选择排序不是稳定的（交换可能会改变相等元素的相对顺序）。它不具备适应性：即使数据部分有序，运行时间也不会改善。

5. Merge Sort | 归并排序

Merge sort is a classic divide‑and‑conquer algorithm. It recursively splits the list into halves until each sublist contains only one element (which is trivially sorted), then merges the sublists back together in sorted order. The merging process compares the first elements of each sublist and places the smaller one into the combined list.

归并排序是一种经典的分治算法。它递归地将列表分成两半，直到每个子列表只包含一个元素（此时自然有序），然后将子列表按顺序合并回来。合并过程会比较每个子列表的第一个元素，并将较小的元素放入合并后的列表中。

Merging two sorted lists:

合并两个已排序列表：

procedure merge(left, right)
    result = []
    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]
        end if
    end while
    append remaining elements of left and right to result
    return result
end procedure

Merge sort always runs in O(n log n) time regardless of the input. It requires O(n) additional space for the merging process (or O(n) for the auxiliary arrays). It is a stable sort. While merge sort is not adaptive in its pure form (it always splits to the base case), it can be optimised to detect already sorted runs.

无论输入如何，归并排序总是在 O(n log n) 时间内运行。合并过程需要 O(n) 额外空间（用于辅助数组）。它是一种稳定的排序。虽然纯归并排序不具备适应性（它总是拆分到基本情况），但可以通过检测已经有序的片段进行优化。

6. Quick Sort | 快速排序

Quick sort is also a divide‑and‑conquer algorithm. It selects a pivot element from the list and partitions the other elements into two sublists according to whether they are less than or greater than the pivot. The sublists are then recursively sorted. The pivot selection strategy dramatically affects performance.

快速排序也是一种分治算法。它从列表中选择一个基准元素（pivot），并将其他元素根据是否小于或大于基准划分到两个子列表中。然后递归地对子列表进行排序。基准的选择策略对性能有显著影响。

A simple partition pseudocode (Lomuto scheme):

一个简单的划分伪代码（Lomuto 方案）：

procedure quickSort(A, low, high)
    if low < high then
        pivotIndex = partition(A, low, high)
        quickSort(A, low, pivotIndex - 1)
        quickSort(A, pivotIndex + 1, high)
    end if
end procedure

procedure partition(A, low, high)
    pivot = A[high]
    i = low - 1
    for j = low to high-1
        if A[j] < pivot then
            i = i + 1
            swap A[i] and A[j]
        end if
    end for
    swap A[i+1] and A[high]
    return i + 1
end procedure

Worst‑case time complexity is O(n²) when the pivot is always the smallest or largest element (e.g. already sorted data with a poor pivot choice). Average‑case is O(n log n). With a good pivot selection (e.g. random or median‑of‑three), quick sort is very fast in practice. It sorts in place, requiring O(log n) space on the call stack. Quick sort is not stable (partitioning can change the order of equal elements).

最坏情况时间复杂度为 O(n²)，当基准总是最小或最大元素时（例如，已排序数据且基准选择不佳）。平均情况为 O(n log n)。如果基准选择得当（如随机选取或三数取中），快速排序在实践中非常快。它是原地排序，调用栈需要 O(log n) 空间。快速排序不稳定（划分过程可能改变相等元素的顺序）。

7. Comparing Sorting Algorithms: Time and Space Complexity | 排序算法比较：时间复杂度与空间复杂度

A clear understanding of resource usage is essential for exam success. The table below summarises the complexities of the five algorithms. All complexities are expressed in Big O notation.

清楚理解资源使用情况是考试成功的关键。下表总结了五种算法的复杂度。所有复杂度均以大 O 符号表示。

Algorithm	Best Time	Average Time	Worst Time	Space	Stable?
Bubble Sort	O(n)	O(n²)	O(n²)	O(1)	Yes
Insertion Sort	O(n)	O(n²)	O(n²)	O(1)	Yes
Selection Sort	O(n²)	O(n²)	O(n²)	O(1)	No
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)	Yes
Quick Sort	O(n log n)	O(n log n)	O(n²)	O(log n) (stack)	No

In exams, you may need to justify why merge sort is preferred for linked lists (no random access overhead, O(1) extra space if done carefully) or why quick sort is often faster than merge sort in practice (better cache locality, smaller constant factors). Knowing these trade‑offs can earn high marks.

在考试中，你可能需要解释为什么归并排序更适合链表（无需随机访问带来的开销，若仔细实现可以做到 O(1) 额外空间），或者为什么快速排序在实践中往往比归并排序更快（更好的缓存局部性，更小的常数因子）。理解这些权衡可以让你获得高分。

8. Stability and Adaptivity | 稳定性与适应性

A sorting algorithm is stable if two objects with the same key appear in the same order in the sorted output as they did in the input. Stability matters when sorting by multiple fields: for instance, if you sort a list of students first by name and then by grade, a stable sort preserves the alphabetical order within each grade.

如果两个具有相同键值的对象在排序后的输出中保持与输入相同的相对顺序，则该排序算法是稳定的。当按多个字段排序时，稳定性很重要：例如，如果你先按姓名对学生列表排序，再按成绩排序，稳定排序会在每个成绩分组中保持字母顺序。

Bubble sort, insertion sort, and merge sort are stable. Selection sort and the typical in‑place quick sort are not. An algorithm is adaptive if it takes advantage of existing order in the input to run faster. Insertion sort and bubble sort (with early termination) are adaptive; selection sort is not. Merge sort can be made adaptive with techniques like Timsort, but the standard version is not.

冒泡排序、插入排序和归并排序是稳定的。选择排序和典型的原地快速排序则不是。如果一个算法能利用输入中已有的顺序来加快运行速度，它就是适应性的。插入排序和冒泡排序（带提前终止）是适应性的；选择排序不是。归并排序可以通过如 Timsort 等技术变得具有适应性，但标准版本不是。

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

When given a scenario, you must recommend an appropriate algorithm. Small datasets or nearly sorted data: insertion sort is often the best due to its adaptivity and low overhead. Large datasets with random order: merge sort or quick sort are preferred for their O(n log n) average time. If memory is limited, quick sort’s in‑place nature gives it an edge. When stability is required, choose merge sort or insertion sort over quick sort. For educational purposes, bubble sort and selection sort illustrate fundamental concepts but are rarely used in practice on large data.

面对具体场景时，你必须推荐合适的算法。对于小数据集或接近有序的数据：插入排序通常是最佳选择，因为其适应性和低开销。对于随机顺序的大数据集：归并排序或快速排序因其 O(n log n) 的平均时间而更受青睐。如果内存有限，快速排序的原地特性使其具有优势。当需要稳定性时，应选择归并排序或插入排序而非快速排序。在教学上，冒泡排序和选择排序展示了基本概念，但在处理大量数据时很少实际使用。

Exam questions often ask: “Explain why algorithm X is more efficient than algorithm Y for a given dataset.” Your answer should reference time complexity, adaptivity, number of comparisons/swaps, and memory usage.

考试题目经常会问：“解释为什么算法 X 在给定数据集上比算法 Y 更高效。”你的回答应引用时间复杂度、适应性、比较/交换次数以及内存使用情况。

10. Sorting in Practice: Exam Tips | 排序实战：考试技巧

Trace tables: You will often be asked to complete a trace table showing the state of an array after each pass of a sorting algorithm. Practise manually applying bubble sort, insertion sort, and merge sort to small arrays. Be meticulous with indices and loop boundaries.

跟踪表：你常常需要填写一个跟踪表，显示排序算法每次遍历后数组的状态。练习手动对小型数组应用冒泡排序、插入排序和归并排序。要仔细注意索引和循环边界。

Pseudocode recall: Some exam boards expect you to write or complete pseudocode for these algorithms. Focus on the key loops and conditionals. Understand the role of the “swapped” flag in bubble sort and the “key” variable in insertion sort.

伪代码回忆：某些考试局要求你编写或补全这些算法的伪代码。重点掌握关键的循环和条件语句。理解冒泡排序中“swapped”标志以及插入排序中“key”变量的作用。

Complexity questions: Be prepared to derive or state the worst‑case time complexity given a code snippet. Remember that a single loop over n items is O(n), a nested loop is O(n²), and divide‑and‑conquer with logarithmic depth gives O(n log n).

复杂度问题：做好准备，根据代码片段推导或陈述最坏情况时间复杂度。记住，对 n 个元素进行单层循环是 O(n)，嵌套循环是 O(n²)，而对数深度的分治法则为 O(n log n)。

Comparing algorithms: Use comparative language such as “Merge sort guarantees O(n log n) time, whereas quick sort may degrade to O(n²) on already sorted data with a poor pivot.” This demonstrates deep understanding.

算法比较：使用对比性语言，例如“归并排序保证 O(n log n) 时间，而快速排序在基准选择不佳时可能退化到 O(n²)。”这体现出深入的理解。

Common pitfalls: Confusing the direction of the comparison in bubble sort and insertion sort; forgetting that selection sort always performs n–1 swaps; thinking quick sort uses O(n) extra space (it is in‑place, but recursion stack uses O(log n) space). Avoid these errors in your answers.

常见误区：混淆冒泡排序和插入排序中比较的方向；忘记选择排序总是执行 n–1 次交换；误认为快速排序使用 O(n) 额外空间（它是原地排序，但递归栈使用 O(log n) 空间）。在答案中避免这些错误。

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

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

A-Level Computer Science: Sorting Algorithms – Essential Revision | A-Level 计算机：排序 考点精讲