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

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

Sorting is a fundamental concept in IB Computer Science, appearing in both Standard Level (SL) and Higher Level (HL) syllabi. The ability to arrange data in a particular order—numerical, lexicographic, or based on a key—is essential for efficient searching, merging, and data analysis. This revision guide covers the key sorting algorithms you need to know, their mechanics, pseudocode, complexity analysis, stability, and common exam question types.

排序是IB计算机科学中的一个基础概念，出现在标准级别（SL）和高级级别（HL）的教学大纲中。能够将数据按特定顺序（数值、字典序或基于某个键）排列，对于高效搜索、合并和数据分析至关重要。本复习指南涵盖你需要掌握的关键排序算法、它们的机制、伪代码、复杂度分析、稳定性以及常见的考试题型。

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

Sorting refers to reorganising a collection of data items so that they are arranged in a specified order, typically ascending (smallest to largest) or descending. Sorting algorithms can be classified as internal (all data fits in main memory) or external (data resides on disk). In the IB course, the focus is on internal comparison-based sorting algorithms.

排序是指对一个数据集合进行重新组织，使其按指定顺序（通常是升序或降序）排列。排序算法可分为内部排序（所有数据都能放入主存）和外部排序（数据位于磁盘）。在IB课程中，重点是基于比较的内部排序算法。

Key factors used to evaluate sorting algorithms include time complexity (how the run time grows with input size n), space complexity (extra memory usage), stability (whether equal elements preserve their relative order), and whether the algorithm is in-place (uses a constant amount of extra space).

用于评估排序算法的关键因素包括时间复杂度（运行时间随输入规模n的增长情况）、空间复杂度（额外内存使用）、稳定性（相等元素是否保持其相对顺序）以及算法是否是原地排序（使用常数级额外空间）。

2. Bubble Sort | 冒泡排序

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 a complete pass is made without any swaps, indicating the list is sorted. This algorithm is simple but inefficient for large datasets.

冒泡排序通过反复遍历列表来工作，比较相邻元素并在顺序错误时交换它们。遍历列表的过程不断重复，直到完成一次未发生任何交换的完整遍历，此时表明列表已排序。该算法简单，但对于大数据集效率低下。

Pseudocode:

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 if
        end for
    until not swapped
end procedure

The best-case time complexity occurs when the list is already sorted: only one pass is needed, giving O(n). The worst-case and average-case complexities are O(n²), as each element may need to “bubble up” through the entire list. Bubble Sort is stable (equal elements are not swapped) and in-place O(1) extra space.

最好情况时间复杂度发生在列表已经有序时：只需要一遍遍历，为O(n)。最坏情况和平均时间复杂度是O(n²)，因为每个元素可能都需要“冒泡”到整个列表的末尾。冒泡排序是稳定的（相等元素不会交换），并且是原地排序，额外空间为O(1)。

3. Selection Sort | 选择排序

Selection Sort divides the list into a sorted and an unsorted region. It repeatedly finds the smallest (or largest) element from the unsorted part and swaps it with the leftmost unsorted element, gradually expanding the sorted region. This algorithm performs a fixed number of comparisons, making it inefficient on large lists.

选择排序将列表划分为已排序区域和未排序区域。它重复从未排序部分找到最小（或最大）元素，并将其与未排序部分最左边的元素交换，逐步扩大已排序区域。该算法执行固定次数的比较，因此在大型列表上效率较低。

Pseudocode:

procedure selectionSort(A : list)
    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], A[minIndex])
        end if
    end for
end procedure

The time complexity is O(n²) in all cases (best, average, worst) because of the nested loops. The number of swaps is at most n-1, so Selection Sort can be useful when writes are expensive. However, it is not stable by default, because swapping may change the relative order of equal elements. It is in-place with O(1) extra space.

由于嵌套循环，选择排序在所有情况下（最好、平均、最坏）的时间复杂度都是O(n²)。交换次数最多为n-1，因此在写操作代价高昂时，选择排序可能会很有用。但默认情况下它是不稳定的，因为交换可能改变相等元素的相对顺序。它是原地排序，额外空间为O(1)。

4. Insertion Sort | 插入排序

Insertion Sort builds the final sorted array one item at a time. It iterates through the input elements, removing one element per iteration and inserting it into its correct position within the sorted portion. It is efficient for small or nearly sorted datasets and is often used as part of more advanced algorithms.

插入排序每次构建最终排序数组时添加一个元素。它遍历输入元素，每次迭代取出一个元素并将其插入到已排序部分的正确位置。该算法对于小型或基本有序的数据集效率很高，并且经常被用作更高级算法的一部分。

Pseudocode:

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

The best-case time complexity is O(n) when the list is already sorted, requiring only one comparison per element. The worst-case and average-case complexities are O(n²), occurring when the list is in reverse order. Insertion Sort is stable (equal keys remain in original order) and operates in-place (O(1) extra space).

最好情况时间复杂度为O(n)，当列表已排序时，每个元素只需一次比较。最坏情况和平均时间复杂度为O(n²)，发生在列表完全逆序时。插入排序是稳定的（相等键保持原始顺序），并且是原地排序（O(1)额外空间）。

5. Merge Sort (HL) | 归并排序（HL）

Merge Sort is a divide-and-conquer algorithm that splits the list into two halves, recursively sorts each half, and then merges the sorted halves back together. The merge step compares elements from both halves and inserts the smaller one first. This algorithm guarantees O(n log n) performance but requires additional memory.

归并排序是一种分治算法，它将列表分成两半，递归地对每一半进行排序，然后将两个有序半部分合并。合并步骤比较两个半部分的元素，并优先插入较小的元素。该算法可保证O(n log n)的性能，但需要额外的内存空间。

Pseudocode (high-level):

procedure mergeSort(A, left, right)
    if left < right then
        mid = floor((left + right) / 2)
        mergeSort(A, left, mid)
        mergeSort(A, mid+1, right)
        merge(A, left, mid, right)
    end if
end procedure

Merge Sort has a time complexity of O(n log n) in all cases (best, average, worst) because the division creates log n levels and each merge takes O(n). The space complexity is O(n) due to the need for temporary arrays, which means it is not in-place. However, it is stable: when merging, if two elements are equal, the left one is taken first, preserving order.

归并排序在所有情况下（最好、平均、最坏）的时间复杂度均为O(n log n)，因为划分创建了log n层，每层合并需要O(n)。由于需要临时数组，空间复杂度为O(n)，这意味着它不是原地排序。然而，它是稳定的：在合并时，如果两个元素相等，优先取左侧的元素，从而保持顺序不变。

6. Quicksort (HL) | 快速排序（HL）

Quicksort is another divide-and-conquer algorithm that selects a “pivot” element from the array and partitions the other elements into two sub-arrays according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively. The choice of pivot greatly affects performance.

快速排序是另一种分治算法，它从数组中选择一个“枢轴”元素，并根据其他元素是小于还是大于枢轴将它们划分到两个子数组中。然后对子数组进行递归排序。枢轴的选择极大地影响性能。

Basic pseudocode:

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

The average-case time complexity is O(n log n), while the worst-case is O(n²), occurring when the pivot selection is poor (e.g., always the smallest or largest element). With a good pivot strategy (like median-of-three), worst-case can be avoided in practice. Quicksort is generally not stable, as it may swap distant elements; it is in-place if implemented with Hoare or Lomuto partition schemes, though recursion uses O(log n) stack space on average.

平均情况时间复杂度为O(n log n)，而最坏情况为O(n²)，发生在枢轴选择不佳时（例如总是选择最小或最大元素）。通过良好的枢轴策略（如三数取中法），实践中可以避免最坏情况。快速排序通常不是稳定的，因为它可能交换距离较远的元素；如果用Hoare或Lomuto分区方案实现，它是原地排序，但递归在平均情况下使用O(log n)栈空间。

7. Big-O Notation and Efficiency Analysis | 大O表示法与效率分析

Big-O notation describes the upper bound of an algorithm’s growth rate, focusing on the dominant term as n becomes large. For sorting algorithms, the key operations are comparisons and swaps. IB exam questions often ask you to determine the time complexity of a given algorithm or to compare efficiencies.

大O表示法描述了算法增长率的上限，重点关注当n变大时占主导地位的项。对于排序算法，关键操作是比较和交换。IB考试题目经常要求你确定给定算法的时间复杂度或比较效率。

Constant O(1) – rare for sorting, but applies to single operations like a swap.

常数 O(1) – 在排序中罕见，但适用于交换等单一操作。
Linear O(n) – best-case scenarios for Bubble Sort and Insertion Sort.

线性 O(n) – 冒泡排序和插入排序的最好情况。
Quadratic O(n²) – typical for simple algorithms: Bubble, Selection, Insertion (worst/average).

二次方 O(n²) – 简单算法的典型情况：冒泡、选择、插入排序（最坏/平均）。
Log-linear O(n log n) – efficient algorithms like Merge Sort and Quicksort (average).

线性对数 O(n log n) – 高效算法如归并排序和快速排序（平均）。

Space complexity is also assessed: in-place algorithms use O(1) extra memory, while Merge Sort uses O(n). Understanding these distinctions is crucial for answering “suggest an appropriate algorithm” questions.

空间复杂度也会被评估：原地算法使用O(1)额外内存，而归并排序使用O(n)。理解这些区别对于回答“推荐一个合适的算法”类问题至关重要。

8. Comparison Table of Sorting Algorithms | 排序算法对比表

The table below summarises the key properties of the five core sorting algorithms for quick revision.

下表总结了五种核心排序算法的关键特性，便于快速复习。

Algorithm \| 算法	Best \| 最好	Average \| 平均	Worst \| 最坏	Space \| 空间	Stable? \| 稳定性	In-place? \| 原地性
Bubble Sort	O(n)	O(n²)	O(n²)	O(1)	Yes	Yes
Selection Sort	O(n²)	O(n²)	O(n²)	O(1)	No	Yes
Insertion Sort	O(n)	O(n²)	O(n²)	O(1)	Yes	Yes
Merge Sort (HL)	O(n log n)	O(n log n)	O(n log n)	O(n)	Yes	No
Quicksort (HL)	O(n log n)	O(n log n)	O(n²)	O(log n)*	Typically No	Yes (in-place version)

*Average-case stack space for the recursive implementation. The in-place variant uses O(1) extra data memory.

*递归实现的平均栈空间。原地变体仅使用O(1)额外数据内存。

9. Stability and In-Place Sorting | 稳定性和原地排序

Stability means that if two records have equal keys, their relative order in the sorted output matches their original order. This property is vital when sorting objects by multiple criteria (e.g., sort by surname then by first name). Stable algorithms include Bubble Sort, Insertion Sort, and Merge Sort. Selection Sort and typical Quicksort implementations are unstable.

稳定性意味着如果两条记录的键相等，则在排序后的输出中它们的相对顺序与原始顺序一致。当按多个条件对对象进行排序时（例如先按姓氏再按名字排序），这一特性至关重要。稳定的算法包括冒泡排序、插入排序和归并排序。选择排序和常见的快速排序实现是不稳定的。

An in-place algorithm operates directly on the input data structure, requiring only a constant amount of extra memory. This is important when memory is limited. All three simple sorts are in-place, as is in-place Quicksort; Merge Sort is not in-place unless sophisticated optimisations are applied, which are beyond the IB syllabus.

原地算法直接在输入数据结构上操作，仅需要常数量的额外内存。这在内存有限时非常重要。三种简单排序都是原地排序，原地版快速排序也是；归并排序不是原地排序，除非应用了复杂的优化，这些超出了IB大纲范围。

10. Tracing and Exam Tips | 追踪与应试技巧

IB Computer Science exams often include tracing exercises: you are given an unsorted array and must show the state of the array after each pass of a specified algorithm. Practice tracing Bubble Sort (showing the bubbling action), Selection Sort (showing the min-index selection), and Merge Sort (showing the recursive splitting and merging).

IB计算机科学考试常包括追踪练习：给定一个未排序的数组，你必须展示指定算法在每一趟遍历后数组的状态。建议练习追踪冒泡排序（展示冒泡过程）、选择排序（展示最小索引的选择）和归并排序（展示递归拆分和合并）。

When asked to “suggest an appropriate algorithm and justify your choice,” consider factors such as input size, whether the data is almost sorted, memory constraints, and the need for stability.

当被要求“推荐一个合适的算法并说明理由”时，需考虑输入规模、数据是否接近有序、内存限制以及稳定性需求等因素。
If the data is small or nearly sorted, Insertion Sort is often the best choice due to its O(n) best-case and low overhead.

如果数据规模小或接近有序，插入排序通常是最佳选择，因为它有O(n)的最好情况和低开销。
For large, general-purpose sorting, Merge Sort guarantees O(n log n) and stability, while Quicksort usually outperforms in practice due to cache efficiency and smaller constants, despite its worst-case O(n²).

对于大型通用排序，归并排序可保证O(n log n)和稳定性，而快速排序在实践中往往因缓存效率和更小的常数因子而表现更优，尽管最坏情况为O(n²)。

Always label your answers clearly, use correct Big-O expressions, and show your working when

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

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

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