📚 Sorting Algorithms: Key Exam Points for IB & Edexcel | IB 与 Edexcel 排序算法考点精讲
Sorting is the process of arranging data in a particular order, typically ascending or descending. For IB and Edexcel Computer Science, understanding sorting algorithms is critical for algorithm efficiency, problem-solving, and exam success. This guide covers the most essential sorting algorithms, their properties, complexities, and how to answer exam questions effectively.
排序是将数据按特定顺序（通常是升序或降序）排列的过程。对于 IB 和 Edexcel 计算机科学课程，理解排序算法对于算法效率、问题求解和考试成功至关重要。本指南涵盖了最重要的排序算法、它们的性质、复杂度以及如何有效应对考试题目。
1. Introduction to Sorting | 排序简介
Sorting involves rearranging elements in a list or array according to a comparison rule. It is a basic operation used in many computer programs, such as searching, data analysis, and displaying results.
排序涉及根据比较规则重新排列列表或数组中的元素。这是许多计算机程序中使用的基本操作，例如搜索、数据分析和显示结果。
In the IB and Edexcel syllabi, you are expected to know how common sorting algorithms work, be able to trace them on given data, understand their efficiency, and write pseudo-code if required.
在 IB 和 Edexcel 的教学大纲中，你需要了解常见排序算法的工作原理，能够在给定数据上跟踪它们，理解它们的效率，并在需要时编写伪代码。
2. Key Concepts: Stability, In-place, and Comparison | 关键概念：稳定性、原地和比较排序
A sorting algorithm is stable if it preserves the relative order of equal elements. For example, if two items have the same key, they appear in the same order in the output as in the input. Stability matters when sorting by multiple keys.
如果排序算法保持相等元素的相对顺序，则它是稳定的。例如，如果两个项目具有相同的键，它们在输出中出现的顺序与输入中相同。在按多个键排序时，稳定性很重要。
An in-place algorithm uses a constant amount (O(1)) of extra memory space, while algorithms like merge sort require additional memory proportional to the input size (O(n)).
原地算法使用常量大小（O(1)）的额外内存空间，而像归并排序这样的算法需要与输入大小成比例的额外内存（O(n)）。
Comparison-based sorting algorithms determine the order by comparing elements. The theoretical lower bound for comparison sorts is O(n log n) in the average case. Non-comparison sorts (e.g., counting sort) can achieve O(n) under certain conditions but are not always applicable.
基于比较的排序算法通过比较元素来确定顺序。比较排序在平均情况下的理论下界是 O(n log n)。非比较排序（例如计数排序）在特定条件下可以达到 O(n)，但并不总是适用。
3. Bubble Sort | 冒泡排序
Bubble Sort repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The largest unsorted element ‘bubbles’ to the end in each pass. It continues until no swaps are needed.
冒泡排序重复遍历列表，比较相邻元素，如果顺序错误则交换它们。在每一趟中，最大的未排序元素会“冒泡”到末尾。它一直持续到不需要交换为止。
Complexity: Best O(n) with early exit optimisation, average and worst O(n²). It is stable and in-place (O(1) extra space). In exams, you may be asked to show the state after each pass or to optimize with a flag to detect no swaps.
复杂度：经过优化提前退出的最好情况 O(n)，平均和最坏情况 O(n²)。它是稳定的且原地（O(1)额外空间）。在考试中，你可能被要求显示每一趟之后的状态，或使用标志检测无交换进行优化。
4. Selection Sort | 选择排序
Selection Sort divides the 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 step right.
选择排序将列表分为已排序区域和未排序区域。它反复从未排序区域中选择最小（或最大）的元素，将其与最左边的未排序元素交换，并将边界向右移动一步。
Complexity: Always O(n²) comparisons, O(n) swaps. It is unstable (can disrupt relative order of equal elements) but in-place. Selection sort performs well when writing to memory is costly because it minimizes swaps.
复杂度：始终进行 O(n²) 次比较和 O(n) 次交换。它不稳定（可能打乱相等元素的相对顺序），但是原地的。当写入内存的代价很高时，选择排序表现良好，因为它最小化了交换次数。
5. Insertion Sort | 插入排序
Insertion Sort builds the sorted list one element at a time by taking each element from the input and inserting it into its correct position within the already sorted part. It shifts elements to make room.
插入排序逐个从输入中取出每个元素，并将其插入到已排序部分的正确位置，从而逐步构建有序列表。它通过移动元素来腾出空间。
Complexity: Best O(n) when data is nearly sorted, average and worst O(n²). It is stable and in-place. Insertion sort is efficient for small datasets and is often used as part of hybrid algorithms like Timsort.
复杂度：当数据接近有序时最好情况 O(n)，平均和最坏情况 O(n²)。它是稳定的且原地。插入排序对小数据集高效，常用于混合算法如 Timsort 中。
6. Merge Sort | 归并排序
Merge Sort is a divide-and-conquer algorithm. It recursively splits the array into halves, sorts each half, and then merges the two sorted halves back together. The merging step combines them in sorted order.
归并排序是一种分治算法。它递归地将数组分成两半，对每一半进行排序，然后将两半有序合并。合并步骤将它们按排序顺序组合在一起。
Complexity: O(n log n) in all cases (best, average, worst). It is stable but not in-place as it requires O(n) extra space for the merge process. This predictable performance makes it a good choice for large datasets in external sorting.
复杂度：在所有情况下（最好、平均、最坏）均为 O(n log n)。它是稳定的，但不是原地，因为合并过程需要 O(n) 的额外空间。这种可预测的性能使其成为外部排序中大型数据集的好选择。
7. Quick Sort | 快速排序
Quick Sort also uses divide and conquer. It picks a pivot element and partitions the array so that elements less than pivot come before it, and greater come after. It then recursively sorts the sub-arrays.
快速排序同样使用分治法。它选择一个基准元素并对数组进行分区，使得小于基准的元素位于其左侧，大于基准的位于右侧。然后递归地对子数组排序。
Complexity: Best and average O(n log n), worst O(n²) when the pivot selection is poor (e.g., already sorted array with first element as pivot). It is not stable but is in-place (O(log n) space for recursion stack). Randomising the pivot or using median-of-three improves performance.
复杂度：最好和平均 O(n log n)，当基准选择不佳时（例如，已排序数组且以第一个元素为基准）最坏 O(n²)。它不稳定，但是原地（递归栈空间 O(log n)）。随机化基准或使用三数取中法可以提高性能。
8. Heap Sort: A Brief Look | 堆排序：简要介绍
Heap Sort uses a binary heap data structure. It first builds a max heap from the data, then repeatedly extracts the maximum element and places it at the end, restoring the heap property.
堆排序使用二叉堆数据结构。它首先根据数据构建最大堆，然后重复提取最大元素并将其放在末尾，同时恢复堆的性质。
Complexity: O(n log n) in all cases, in-place O(1) space, but unstable. It is often compared with quick sort and merge sort in terms of practical speed and memory usage.
复杂度：所有情况下 O(n log n)，原地 O(1) 空间，但不稳定。在实际速度和内存使用上，常将它与快速排序和归并排序进行比较。
9. Comparing Time and Space Complexities | 时间与空间复杂度对比
The table below summarises the key complexities for the sorting algorithms covered. Use it to quickly reference exam questions on efficiency.
下表总结了所涵盖排序算法的主要复杂度。可用来快速参考效率相关的考试题目。
| Algorithm | Best | Average | Worst | Space | Stable |
|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(
Published by TutorHao | IB Computer Science Revision Series | aleveler.com 更多咨询请联系16621398022（同微信） CommentsMore posts |
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导