GESP 四级 · GESP 202506 C++ 四级 第 22 题

无论初始数组是否有序，选择排序都执行 $O(n^2)$ 次比较。

答案A。选择排序每轮找最小值交换到前面。补全时要确保比较的是当前元素与当前最小值。

选择排序每轮找到最小值下标后与当前位置交换。注意比较的是数组元素值而不是下标。

【考点】排序算法复杂度分析｜选择排序原理｜最坏/最好情况比较次数

🎯 考纲定位 命题人卡住学生"认为有序可减少比较"的错觉，考察对选择排序固定比较次数的掌握，属于算法复杂度基础中的排序模块。

🧠 解题思维 选择排序每一轮都遍历剩余未排序部分寻找最小值，第一轮比较 n-1 次，第二轮 n-2 次……直至最后 1 次，总次数为 (n-1)+(n-2)+…+1=n(n-1)/2，即 O(n²)。关键点在于：无论数组初始是否有序，算法始终执行完整遍历，不会因元素已就位而跳过比较——这是选择排序与冒泡、插入排序的本质区别。

🪤 陷阱拆解 错误选项 B 诱使学生混淆选择排序与冒泡/插入排序的"提前终止"特性，或误以为"有序"意味着比较次数减半；题目阴险处在于"无论"二字——它排除了任何基于输入状态的优化可能，直接锁定算法固定行为。若只背结论不懂原理，极易将"有序"与"比较次数减少"建立错误关联。

🔄 反命题思维 若把"比较"改为"交换"，结论将变为 O(n)；若改成"冒泡排序"，有序时比较次数可降为 O(n)。刷到类似题先问：命题人想考我排序的哪类不变性？