考纲要求
- 理解排序是把一组数据按指定关键字重新排列，关键字可以升序或降序。
- 理解稳定排序的含义：关键字相等的元素在排序后保持原有相对顺序。
- 能判断常见排序算法是否稳定，例如冒泡、插入排序稳定，选择排序通常不稳定。
- 能根据题目是否需要保持原顺序选择排序方法。
典型题型
- 给出带相同关键字的记录，判断排序后顺序是否改变。
- 判断某种排序方法是否稳定。
- 为具体场景选择合适的排序方式。
常见错误
- 把「有序」和「稳定」混为一谈，稳定说的是相同关键字之间的相对顺序。
- 认为所有排序都稳定，忽略选择排序中远距离交换会打乱相同元素的顺序。
- 只比较关键字不看附加信息，导致同分记录的顺序被意外改变。
- 以为稳定排序一定更快，稳定性和效率是两个独立维度。
深入理解
稳定性说的是「相同关键字」
如果两个元素的排序关键字相同，排序后它们的相对顺序与排序前一致，这个排序算法就是稳定的；如果可能被调换，就是不稳定的。注意比较的对象是相同关键字之间，不是任意两个元素。
为什么需要稳定？因为实际排序常常按「主关键字 + 次关键字」进行。例如先按学号排好，再按成绩排；如果第二次排序是稳定的，成绩相同的学生仍保持学号顺序，一次排序就完成了两级排序。不稳定的排序会打乱这个次序，还得额外处理。
哪些稳定，哪些不稳定
- 稳定：冒泡排序、插入排序、归并排序。
- 不稳定：选择排序、快速排序、堆排序、希尔排序。
判断依据是「交换时会不会跨越相等元素」。冒泡和插入只交换相邻元素，相等的不动，所以稳定；选择排序每轮把最小值换到前面，可能把后面一个相等元素甩到前面去，所以不稳定；快速排序的分区过程会大范围搬动元素，同样不稳定。
记忆技巧：名字里带「归并」和「插入」「冒泡」的稳定，其余基础排序都不稳定。
用例子判断只要一次反例
给一个具体序列和一种排序，问「排序后两个相等元素的先后」时，不需要完整跑完，只要找出第一处会打破顺序的操作即可。例如序列 3a, 3b, 1 用选择排序：第一轮把 1 与 3a 交换，得到 1, 3b, 3a，相等元素的顺序已经反了，说明不稳定。
反过来要证明稳定，不能只举一个例子，得说明算法在任何情况下都不会跨越相等元素——对冒泡、插入来说，理由是它们只交换严格大于的前一个元素。
自编例题
同分考生的排名
5 名考生按成绩排序，两名 90 分考生的原始顺序是甲在前、乙在后。用哪种排序能保证排序后甲仍在乙前面？
stable_sort(v.begin(), v.end(), [](const auto &x, const auto &y) {
return x.score > y.score;
});按成绩比较时甲乙关键字相等，能否保持原有顺序取决于排序算法是否稳定。stable_sort 保证相等元素维持输入顺序，普通 sort 不保证。如果题目对同分顺序有要求，要么使用稳定排序，要么在比较函数里加入第二关键字，例如按原始编号升序，这样排序结果就与算法是否稳定无关。两种做法中，后者更不容易受实现细节影响。
相关真题
这块内容在整条路线里的位置：GESP C++ 4 级备考路径。
READY TO START
开始练习
先做一套本级别测评，报告会指出哪些知识点需要重点补；再回到本页对照考纲要求逐条核对，把不确定的条目记下来集中练。
常见问题
稳定性有什么用？
当记录有多个字段、只按其中一个字段排序时，稳定性可以保留其他字段原有的顺序，避免二次排序打乱已有结果。
C++ 的 sort 稳定吗？
std::sort 不保证稳定，底层通常是混合排序。需要稳定时使用 std::stable_sort，或者在比较函数里补充第二关键字。
怎么让同分保持原顺序？
使用稳定排序，或者在比较函数中当主关键字相等时比较记录原始下标，强制同分记录按原始顺序排列。