GESP 四级 · GESP 202606 C++ 四级 第 19 题

选择排序算法在寻找每一轮最小值时，如果遇到相等的元素不进行交换，则选择排序是一种稳定的排序算法。

选择排序每轮找到未排序部分的最小值，与未排序部分的第一个元素交换。正确答案B。

冒泡和插入排序是稳定的，选择排序不稳定。稳定=相等元素的相对顺序不变。

【考点】稳定性｜排序算法｜选择排序

1. 考纲定位：本题考查"排序算法稳定性"这一核心概念，在 GESP 大纲中属于数据结构与算法模块。命题人专门设置此题，意在卡住考生"混淆'相等元素不交换'与'算法稳定性'"的认知盲区——很多学生凭直觉认为"不交换就不会乱序"，却忽略了选择排序"每轮选最小值并交换"的操作本身就会打乱相等元素的相对位置。

2. 解题思维：稳定性定义为"相等元素排序后相对顺序不变"。选择排序每轮会找到当前区间最小值并与当前位置交换——假设数组中两个相同最小值，先出现的会在后续轮次被选为最小值并交换到前面，后出现的则留在后面，导致相对顺序颠倒。因此无论是否对相等元素额外处理，选择排序都不稳定。此类题通法：先复述定义，再模拟算法关键步骤，看是否破坏相对顺序。

3. 陷阱拆解：题干"遇到相等的元素不进行交换"是典型误导表述。命题人利用"不交换=稳定"的直觉陷阱，让只背结论的考生误选 A。最阴险的细节在于"稳定性取决于算法整体流程，而非单次交换行为"——即使某次未交换，后续步骤仍会改变相等元素的先后。若只盯着"不交换"三个字而忽略选择过程，必然掉坑。

4. 反命题思维：若将题干改为"冒泡排序在相等元素不交换时是否稳定"，答案即为 A（冒泡排序天然稳定）。这类题目核心不是记忆结论，而是理解算法步骤与稳定性定义的映射关系。刷到同类题先问自己：该算法是否通过交换/移动改变了相等元素的相对次序？