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

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

Sorting algorithms are a fundamental topic in Edexcel A-Level Computer Science. You need to understand the mechanics of bubble sort, insertion sort, merge sort, and quick sort, analyse their time and space complexity, and compare their performance and stability. This revision guide covers all essential exam points, with clear step-by-step explanations and comparisons.

排序算法是 Edexcel A-Level 计算机科学中的基础考点。你需要掌握冒泡排序、插入排序、归并排序和快速排序的工作原理，分析它们的时间与空间复杂度，并比较其性能和稳定性。本考点精讲涵盖所有重要考试要点，通过清晰的步骤说明与对比，帮助你系统复习。

1. Introduction to Sorting | 排序简介

Sorting is the process of arranging elements in a list in a specific order, typically ascending or descending. Efficient sorting is crucial for optimising data retrieval and many other algorithms.

排序是将列表中的元素按特定顺序（通常是升序或降序）排列的过程。高效的排序对优化数据检索及许多其他算法至关重要。

Key concepts include in-place sorting (the algorithm uses minimal extra memory, ideally O(1)) and stability (preserving the relative order of equal elements). For A-Level exams you must be able to decide which algorithm is appropriate based on these properties.

关键概念包括原位排序（算法使用最少的额外内存，理想情况为 O(1)）和稳定性（保持相等元素的相对顺序）。在 A-Level 考试中，你必须能根据这些特性判断应选用哪种算法。

2. Bubble Sort Mechanics | 冒泡排序工作原理

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 a complete pass requires no swaps.

冒泡排序反复遍历列表，比较相邻元素并在顺序错误时交换它们。遍历列表的操作会一直重复，直到一整遍遍历都没有发生任何交换为止。

For an array of n elements, after the first pass the largest element ‘bubbles up’ to its correct position at the end. The next pass processes the first n−1 elements, and so on. Example: sorting [5, 1, 4, 2, 8].

对于含有 n 个元素的数组，第一遍遍历后最大的元素会“冒泡”到末尾正确的位置。下一遍遍历处理前 n−1 个元素，依此类推。示例：排序 [5, 1, 4, 2, 8]。

First pass: (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]. Largest element 8 is now at the end.

第一遍：(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]。最大元素 8 现已到达末尾。

A typical pseudocode representation:

FOR i FROM 0 TO n-2
FOR j FROM 0 TO n-i-2
IF arr[j] > arr[j+1] THEN swap(arr[j], arr[j+1])

典型伪代码描述：

FOR i 从 0 到 n-2
FOR j 从 0 到 n-i-2
IF arr[j] > arr[j+1] THEN 交换(arr[j], arr[j+1])

3. Bubble Sort Complexity & Analysis | 冒泡排序复杂度分析

Time complexity: Best case is O(n) when the list is already sorted and an optimised version detects no swaps in one pass. Average and worst case are both O(n²). Space complexity is O(1) as it sorts in-place.

时间复杂度：最好情况为 O(n)（当列表已经有序且优化版本在一次遍历中检测到无交换时）。平均和最坏情况均为 O(n²)。空间复杂度为 O(1)，因为它是原位排序。

Total number of comparisons = (n−1)+(n−2)+…+1 = n(n−1)/2, which belongs to O(n²). Maximum swaps also follow O(n²). Bubble sort is stable because it only swaps adjacent elements when one is strictly greater, never when equal.

总比较次数 = (n−1)+(n−2)+…+1 = n(n−1)/2，属于 O(n²)。最大交换次数也是 O(n²)。冒泡排序是稳定的，因为它仅在相邻元素中严格大于时才交换，相等时不会交换。

Although simple to implement, bubble sort is impractical for large data sets due to its quadratic time behaviour.

虽然实现简单，但由于其二次方时间复杂度，冒泡排序不适用于大规模数据集。

4. Insertion Sort Mechanics | 插入排序工作原理

Insertion sort builds the final sorted array one item at a time. It takes each element from the unsorted part and inserts it into its correct position within the sorted part, shifting larger elements to the right.

插入排序每次将一个元素从未排序部分取出，并将其插入已排序部分的正确位置，同时将较大元素向右移动。

Example: sorting [5, 1, 4, 2, 8]. Start with sorted part containing first element [5]. Take 1, insert before 5 → [1,5]. Take 4, insert between 1 and 5 → [1,4,5]. Take 2, insert after 1 → [1,2,4,5]. Take 8, insert at end → [1,2,4,5,8].

示例：排序 [5, 1, 4, 2, 8]。已排序部分初始只含首元素 [5]。取 1，插入 5 之前 → [1,5]。取 4，插入 1 和 5 之间 → [1,4,5]。取 2，插入 1 之后 → [1,2,4,5]。取 8，插入末尾 → [1,2,4,5,8]。

Pseudocode outline:

FOR i FROM 1 TO n-1
key = arr[i]
j = i – 1
WHILE j >= 0 AND arr[j] > key
arr[j+1] = arr[j]
j = j – 1
END WHILE
arr[j+1] = key

伪代码框架：

FOR i 从 1 到 n-1
key = arr[i]
j = i – 1
WHILE j >= 0 AND arr[j] > key
arr[j+1] = arr[j]
j = j – 1
END WHILE
arr[j+1] = key

5. Insertion Sort Complexity & Analysis | 插入排序复杂度分析

Time complexity: Best case O(n) when the array is already sorted (inner while loop never runs). Average and worst case are O(n²). The number of comparisons and shifts in the worst case is approximately n(n−1)/2. Space complexity O(1). Insertion sort is stable.

时间复杂度：最好情况 O(n)（数组已有序时，内层 while 循环从不执行）。平均和最坏情况为 O(n²)。最坏情况下的比较与移动次数约为 n(n−1)/2。空间复杂度 O(1)。插入排序是稳定的。

Insertion sort is efficient for small data sets or partially sorted data. It is often used as a building block in more complex algorithms (e.g., Timsort uses insertion sort for small runs).

插入排序对于小数据集或部分有序数据非常高效。它常被用作更复杂算法的基础模块（例如 Timsort 对小规模分段使用插入排序）。

6. Merge Sort Mechanics | 归并排序工作原理

Merge sort is a divide-and-conquer algorithm. It recursively splits the list into two halves until each sub-list contains one element, then merges the sub-lists back together in sorted order.

归并排序是一种分治算法。它递归地将列表分成两半，直到每个子列表只含一个元素，然后再按顺序将这些子列表合并起来。

Merging step: repeatedly compare the smallest remaining elements of two sorted sub-lists, pick the smaller one, and append it to the output list. Repeat until all elements are processed.

合并步骤：反复比较两个已排序子列表中最小的剩余元素，将更小的那个取出并追加到输出列表。重复直到所有元素处理完毕。

Example: [38, 27, 43, 3]. Split → [38,27] and [43,3]; further split to [38],[27],[43],[3]. Merge [38]&[27] → [27,38]; merge [43]&[3] → [3,43]; merge [27,38]&[3,43] → [3,27,38,43].

示例：[38, 27, 43, 3]。分割 → [38,27] 和 [43,3]；继续分为 [38],[27],[43],[3]。合并 [38] 和 [27] → [27,38]；合并 [43] 和 [3] → [3,43]；合并 [27,38] 和 [3,43] → [3,27,38,43]。

The algorithm uses temporary arrays during merging, which is a key distinguishing factor when comparing space usage.

该算法在合并时使用临时数组，这在比较空间使用时是一个关键的区分因素。

7. Merge Sort Complexity & Analysis | 归并排序复杂度分析

Time complexity: Best, average and worst cases are all O(n log n). The splitting creates log₂ n levels, and each level processes n elements during merging. Space complexity is O(n) because of

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

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

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