GESP 七级 · GESP 202606 C++ 七级 第 9 题

下列关于排序稳定性的说法，正确的是（ ）。

快速排序的核心是划分（partition）：选定基准，将数组分为小于和大于基准的两部分，再递归处理。注意最坏情况发生在数组已有序时。

快排在数组已有序时退化为O(n²)。选基准尽量用三数取中法避免最坏情况。分区时注意边界处理。

【考点】排序稳定性｜冒泡排序机制｜选择/快速排序特性

1. 🎯 考纲定位 本题考查 GESP 七级“排序算法及其性质”模块，核心是“稳定性”与“算法机制”的关联。命题人用一道判断题卡住那些只会背“冒泡稳定”结论、却不懂稳定性的本质（相等元素相对位置不变）的考生——这是七级最典型的“概念陷阱”。

2. 🧠 解题思维 解题先锁定“稳定性”定义：相等元素相对位置不变。分析各算法：冒泡只交换相邻逆序，不会跨越元素，必然稳定；选择排序交换任意最小值与当前位置，会跳越相等元素，不稳定；快速排序分区操作会跨越相等元素，不稳定；稳定排序是保持相对位置，不会改变。

3. 🪤 陷阱拆解 陷阱逐个拆解：A 项“只交换相邻逆序”是稳定性的本质——不跨越相等元素；B 项选择排序用最小值与当前位置交换，会跳越相等元素，不稳定；C 项快速排序分区必然跨越，不稳定；D 项是“稳定排序”定义的直接否定，绝对化表述“一定会改变”是命题人最爱用的偷换概念。只背结论的人会被 B 和 C 迷惑。

4. 🔄 反命题思维 反命题视角：若把冒泡改为“交换任意逆序”，稳定性即刻消失；若把选择排序改为“只交换相邻最小值”，则可能稳定。刷到此类题，先问自己“命题人想考我什么”——是考定义、考机制，还是考边界条件。