考纲要求
- 掌握冒泡排序的相邻比较与交换过程，理解每轮把当前最大值冒到末尾。
- 掌握选择排序每轮找最小值并交换到前面的过程。
- 掌握插入排序把当前元素插入已排序部分的过程。
- 能根据给定初始序列写出若干轮排序后的中间状态。
典型题型
- 给出一组数，要求写出冒泡排序第一轮或第三轮后的序列。
- 补全排序程序的循环边界与交换条件。
- 比较几种排序的比较次数与交换次数。
常见错误
- 冒泡排序内层循环边界写到 n，越界访问。
- 排序方向与题目要求相反，降序写成了升序。
- 选择排序交换时把已排好部分打乱，或交换位置写错。
- 插入排序内层比较时没有把元素后移，直接覆盖导致数据丢失。
深入理解
冒泡：每一轮把最大值送到末尾
冒泡排序每一轮从左到右比较相邻两个元素，前一个大于后一个就交换，一轮结束后最大值落在末尾。第 i 轮结束后，末尾 i 个元素已经有序，所以内层只需要比较到 n - i：
for (int i = 0; i < n - 1; i++)
for (int j = 0; j < n - 1 - i; j++)
if (a[j] > a[j+1]) swap(a[j], a[j+1]);共执行 n - 1 轮。题目问「第 3 轮之后序列是什么样」，只需确定前 3 轮各自把哪个最大值送到末尾，不需要把每一轮完整跑一遍。
选择与插入，思路完全不同
选择排序是每一轮在未排序区间里找最小值，和区间第一个元素交换。它的交换次数最少（最多 n - 1 次），但比较次数固定为 n(n-1)/2，与数据是否有序无关。
插入排序把当前元素插到前面已排序序列的合适位置，像整理手里的扑克牌。它在数据基本有序时非常快（接近 O(n)），最坏才是 O(n²)。三种基础排序的平均复杂度都是 O(n²)，区别在常数、交换次数和对原始数据的敏感程度。
手算中间结果的方法
「排序到第 k 轮时序列长什么样」这类题，做法是只跟踪每一轮的关键变化，不重画整张表：
- 冒泡：记下每轮结束后末尾新增的那个数。
- 选择：记下每轮选出的最小值放在第几个位置。
- 插入：记下前缀有序区扩展到第几个元素。
注意题目里的「第几轮」通常从 1 开始计数，而代码里的循环变量从 0 开始，存在一个偏移，这是手算与写代码对不上时首先要检查的地方。
自编例题
手算冒泡排序的中间状态
对序列 5 2 9 1 7 进行冒泡排序，按升序排列，写出第一轮结束后的序列。
for (int i = 0; i < n - 1; i++)
for (int j = 0; j < n - 1 - i; j++)
if (a[j] > a[j + 1]) swap(a[j], a[j + 1]);第一轮从左到右依次比较相邻元素：5 与 2 交换得 2 5 9 1 7；5 与 9 不交换；9 与 1 交换得 2 5 1 9 7；9 与 7 交换得 2 5 1 7 9。第一轮结束后最大值 9 到达最右端，后续各轮最右端不再参与比较，因此内层循环上限要随轮数减少。手算时建议每交换一次就重写一遍序列，比在脑子里追踪更不容易出错。
相关真题
这块内容在整条路线里的位置：GESP C++ 4 级备考路径。
READY TO START
开始练习
先做一套本级别测评，报告会指出哪些知识点需要重点补；再回到本页对照考纲要求逐条核对，把不确定的条目记下来集中练。
常见问题
冒泡排序和选择排序有什么区别？
冒泡每轮通过相邻交换把最大值推到末尾，交换次数多；选择每轮只找最小值再交换一次，交换次数少但比较次数相同。
排序算法要背代码吗？
需要能写出至少一种完整实现，并理解其余算法的过程。考试常考过程推演和循环边界，死记代码容易在细节上出错。
什么时候直接用 sort？
题目只要求结果有序、不限定算法时可以直接用 sort；要求写出排序过程或指定算法时，必须按题目实现。