CSP-J 入门级 · CSP 2022 入门级第一轮 第 12 题

以下排序算法的常见实现中，哪个选项的说法是错误的：（ ）。

这道题考排序稳定性。拿到题先别急着背结论，想清楚‘什么是稳定’——相等元素相对顺序不变。然后逐个看算法：冒泡只换相邻且不等，插入是后插，归并相等取左，唯独选择排序动不动就跨区间交换，最容易翻车。

很多人把选择排序和冒泡混淆，觉得都是‘选最小放前面’就稳了。其实选择排序是全局找最小再交换，哪怕最小在中间，它也会把第一个元素换过去，瞬间打乱相等元素的顺序。记住口诀：冒泡、插入、归并稳；选择、快排、堆排不稳。

考点与概念

排序的稳定性，指的是：若序列中有两个相等元素，排序后它们的相对先后顺序保持不变。比如原序列中 5a 在 5b 前面，排完序后 5a 还得在 5b 前面。

命题视角

这类题通常不会让你手写代码，而是让你判断某个经典算法的稳定性。命题人喜欢挖坑的地方就是：把‘冒泡’和‘选择’这两个名字相近的算法混在一起考，或者让你从一堆稳定/不稳定算法里挑出那个不稳定的。这道题就是典型的‘找错误说法’，正确答案指向选择排序。

逐个分析选项

• A. 冒泡排序：每次只比较相邻两个，若相等则不交换，所以相等元素的相对顺序永远不会被破坏，稳定。
• B. 简单选择排序：每轮在整个未排序区间里找最小值，然后和区间第一个元素交换。一旦最小值不在第一个位置，交换就会把后面某个相等的元素‘换到前面’，从而破坏稳定性，不稳定。
• C. 简单插入排序：把当前元素插入到前面已排好序的部分里，插入时遇到相等的元素会放在它后面（后插），因此相等元素的相对顺序不变，稳定。
• D. 归并排序：合并两个有序子序列时，若两端元素相等，通常规定取左边（或右边）的，这种约定保证了相等元素不会交叉，稳定。

反例演示（为什么选择排序不稳）

考虑序列：[5a, 5b, 1]（5a 和 5b 相等，且 5a 在前）。

1. 第一轮：在整个区间找最小，发现是 1，它与位置 1 的 5a 交换 → [1, 5b, 5a]。 2. 此时 5a 跑到了 5b 后面，相对顺序被颠倒了。

因此，简单选择排序不稳定，选项 B 的说法错误。

避坑提醒

• 别把‘选择最小’等同于‘稳定’。稳定性看的是交换是否可能跨越相等元素，而不是看算法是否‘选得对’。
• 记住稳定排序的三巨头：冒泡、插入、归并；其余常见算法（选择、快排、堆排）都是不稳定的。

考频与趋势

排序稳定性是 CSP 入门级的高频考点。题库中排序相关题目共 249 道，覆盖 2008–2026 年，其中 2024 年已达 51 题，2025 年更是飙到 57 题，2026 年有 50 题，可见近年来出题密度持续上升。就赛事分布而言，GESP 五级 74 题、CSP 入门级 44 题、GESP 四级 39 题、GESP 八级 27 题、GESP 七级 26 题、GESP 六级 12 题、NOIP 提高组初赛 12 题、CSP 提高级 9 题、NOIP 普及组初赛 6 题。入门级和 GESP 五级、四级是出现频率最高的三个级别，说明稳定性这类基础概念在低级别考试中反复出现，考生必须牢固掌握。

预测

从近年数据看，2024–2026 年排序相关题目数量明显增加，且 2025 年达到峰值（57 题）。虽然目前缺乏直接针对‘稳定性’单独统计的年度数据，但结合整体趋势和命题习惯，可以合理预测：未来几年（2027 及以后）排序稳定性仍将是 CSP 入门级和 GESP 五级、四级的必考内容，甚至可能出现更复杂的组合场景（如让你判断多个算法同时作用后的稳定性）。暂无足够依据预测具体年份或题目形式，但‘记住稳定三巨头，其余不稳’这一核心结论大概率继续有效。