【GESP】C++四级考试大纲知识点梳理, (7) 排序算法基本概念
GESP C++四级官方考试大纲中，共有11条考点，本文针对第6条考点进行分析介绍。
（7）掌握排序算法的概念，了解内排序和外排序的概念及差别，理解排序算法的时间复杂度、空间复杂度、使用场景以及稳定性。
四级其他考点回顾：
排序算法是计算机科学中的核心概念，用于将数据按特定顺序（如升序或降序）排列，广泛应用于数据处理和分析。
一、排序算法的概念
排序算法是将无序数据序列按特定规则（如数值大小）排列的方法。它们是算法设计的基础，常见于数据库查询、文件系统管理和搜索优化。掌握排序不仅能提高编程能力，更是理解更高级算法（如搜索、分治、动态规划等）的前提。
根据数据存储位置，排序算法可分为内排序和外排序。
二、内排序与外排序
2.1 内排序
指所有待排序数据能完全加载到主内存（RAM）中进行处理。由于数据直接在内存操作，访问速度快，适合数据量较小的情况。常见内排序算法包括：
- 冒泡排序（Bubble Sort）：通过比较相邻元素交换，逐步将最大或最小元素“冒泡”到正确位置。
- 快速排序（Quicksort）：通过分区（Partition）选择基准元素，递归排序子数组。
- 归并排序（Merge Sort）：将数组递归分为两半，分别排序后合并。
- 插入排序（Insertion Sort）：逐个插入元素到已排序部分。
- 选择排序（Selection Sort）：每次选择最小（或最大）元素交换到正确位置。
- 堆排序（Heap Sort）：利用堆数据结构，构建最大或最小堆后排序。
2.2 外排序
与内排序相反，指数据无法完全加载到内存的排序，数据通常存储在外部设备（如硬盘）上，适用于数据量过大，无法一次性加载到内存的情况。
外排序通过分块处理实现：将数据分成小块，分别排序后逐步合并。典型外排序算法是外部归并排序，它将数据分成适合内存的块，使用内排序（如快速排序）排序每个块，然后通过多路归并合并成最终排序结果。
2.3 内外排序差异对比
- 数据存储位置：内排序数据在内存，访问快；外排序数据在外部存储，需读写操作。
- 速度：内排序因内存访问快，效率高；外排序受限于外部存储速度，较慢。
- 适用场景：内排序适合小规模数据，如几千到几万条记录；外排序用于大规模数据，如数百万或亿级记录，常见于数据库排序或日志处理。
例如，假设有900MB数据，内存仅100MB可用，外部归并排序可按以下步骤:
- 读100MB数据到内存，用快速排序排序后写回磁盘。
- 重复直到所有数据分块排序（生成9个100MB排序块）。
- 读每个块的前10MB到内存，进行9路归并，逐步输出到最终文件。
三、算法排序的时间复杂度与空间复杂度
- 时间复杂度：衡量算法运行时间随输入规模（$n$，元素个数）增长的趋势，通常用大$O$表示。
- $O(n^2)$：如冒泡排序、插入排序、选择排序，适合小数据集，但在大规模数据上效率低。
- $O(n \log n)$：如归并排序、堆排序、快速排序（平均情况），是高效算法，适合大多数场景。
- 例如，冒泡排序通过反复比较相邻元素交换，时间复杂度为$O(n^2)$；归并排序通过递归分治和合并，时间复杂度为$O(n \log n)$。
- 空间复杂度：表示算法使用的额外内存。
- $O(1)$：原地算法，如冒泡排序、堆排序，只需常量级额外空间。
- $O(n)$：如归并排序，需额外数组存储合并结果。
- 快速排序的空间复杂度为$O(\log n)$，主要用于递归调用栈。
四、排序算法稳定性
稳定性是指排序后，相等元素的相对顺序是否与输入时一致。这在多条件排序中尤为重要，例如先按成绩排序，再按姓名排序时，需保留成绩排序的原始顺序。
- 稳定算法：如冒泡排序、插入排序、归并排序，确保相等元素顺序不变。
- 不稳定算法：如选择排序、快速排序、堆排序，可能改变相等元素的相对顺序。
- 重要性：稳定性在以下场景关键：
- 多字段排序：如先按部门排序，再按员工ID排序，需保持部门内ID顺序。
- 数据分析：如统计词频，按频次排序后需保持字母顺序。
例如，假设数组为[3, 1, 4, 1, 5]，两个“1”在输入中顺序为后出现者先，稳定排序如归并排序会保持此顺序；不稳定排序如快速排序可能交换“1”的位置。
五、排序算法使用场景
选择排序算法需根据具体需求：
- 数据规模：小数据集（如几百个元素）可使用简单算法如插入排序；大数据集（如百万级）优先选择O(n log n)算法如归并排序或快速排序。
- 内存限制：内存有限时，优先原地算法如堆排序；内存充足可选择归并排序。
- 数据特性：若数据近乎有序，插入排序效率高；若数据随机分布，快速排序表现优。
- 稳定性需求：如需保持相等元素的相对顺序（如多字段排序），选择稳定算法如归并排序；若无此需求，可用不稳定但高效的快速排序。
六、排序算法总结表格
| 排序算法 | 时间复杂度（平均） | 空间复杂度 | 是否稳定 | 适用场景 |
|---|---|---|---|---|
| 冒泡排序 | $O(n^2)$ | $O(1)$ | ✅ | 简单、小数据集 |
| 插入排序 | $O(n^2)$ | $O(1)$ | ✅ | 近乎有序数据 |
| 选择排序 | $O(n^2)$ | $O(1)$ | ❌ | 数据交换开销不大 |
| 快速排序 | $O(n \log n)$ | $O(\log n)$ | ❌ | 一般场景，效率高 |
| 归并排序 | $O(n \log n)$ | $O(n)$ | ✅ | 大数据、需要稳定性 |
| 堆排序 | $O(n \log n)$ | $O(1)$ | ❌ | 不要求稳定性 |
| 计数排序 | $O(n + k)$ | $O(k)$ | ✅ | 整数、小范围数据 |
| 基数排序 | $O(nk)$ | $O(n + k)$ | ✅ | 整数或定长字符串 |
| 桶排序 | $O(n + k)$ | $O(n + k)$ | ✅ | 分布均匀的浮点数 |
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP各级别考纲要点、知识拓展和练习题目清单详见C++学习项目主页
“luogu-”系列题目已加入洛谷Java、C++初学团队，作业清单，可在线评测，团队名额有限，欢迎加入。
“bcqm-”系列题目可在编程启蒙题库进行在线评测。