北京海淀区信息学竞赛 · 2024 北京市海淀区信息学竞赛（初赛）试题 第 5 题

下列有关选择排序算法的叙述中，正确的是（ ）

这题考排序算法特性，先看四个选项里哪个是绝对对的，再逐个排除干扰项，重点盯住‘稳定性’和‘比较次数是否随初始状态变化’这两个坑。

容易把冒泡和选择排序的速度混为一谈，其实冒泡在最好情况能退化成线性时间，而选择排序无论怎么排都得跑满 n(n-1)/2 次比较，所以 B 错。也容易误以为选择排序的比较次数会受初始状态影响，其实它每次只找最小值，跟数据怎么摆没关系，D 错。C 说时间复杂度是 O(n) 更是离谱，那是线性排序（如计数排序）的事，选择排序是 O(n²)。

这道题考查的是排序算法的基本概念，尤其要分清‘稳定性’和‘比较次数’这两个关键点。

先说核心概念：稳定排序是指相等元素的相对顺序在排序后保持不变，比如冒泡、插入、归并都是稳定的；而选择排序、快速排序、堆排序则是不稳定的，因为它们在交换过程中可能会打乱相等元素的先后次序。所以 A 选项说“选择排序是不稳定的”完全正确，这是本题的题眼。

再看命题人怎么挖坑：B 选项故意把冒泡和选择排序的速度拿来比。冒泡排序虽然最坏也是 O(n²)，但它有个很特殊的地方——如果数组已经有序，它只要走一遍就能结束，最好情况是 O(n)；而选择排序不管数组有没有序，它都得老老实实跑 n(n-1)/2 次比较，时间复杂度永远是 O(n²)。因此说“选择排序速度快于冒泡”是错的，B 排除。

C 选项更是离谱，直接说选择排序时间复杂度是 O(n)。要知道，O(n) 的线性排序（如计数排序、基数排序）根本不需要比较，而是利用数据范围做桶或按位分配；选择排序必须两两比较才能找到最小值，复杂度只能是 O(n²)。C 错得离谱，排除。

D 选项说比较次数与初始状态相关。其实选择排序每次只负责从剩余未排序部分挑一个最小的放到前面，这个过程跟数据原本怎么摆毫无关系，比较次数固定为 n(n-1)/2，跟初始状态无关。D 错，排除。

综上，只有 A 是绝对正确的。

考频与趋势：从历年海淀区信息学竞赛真题来看，排序算法的特性（稳定/不稳定、时间复杂度、比较次数）是高频考点，尤其喜欢用‘冒泡 vs 选择’‘比较次数是否随初始状态变化’这类对比来设陷阱。这类概念题在 CSP-J/S 初赛中也经常出现，属于必须熟记的基础。

预测：基于现有数据，未来考题大概率仍会围绕‘稳定性’和‘比较次数’出题，可能会换个场景（比如给出具体数组问是否稳定，或者问某种排序在特定情况下的比较次数）。暂无足够依据预测具体题目形式，但掌握这些核心特性是应对万变考题的定海神针。