BCSP-X · 2024 BCSP-X 上半年活动基础知识测评（小学高年级组） 第 14 题

以下排序算法中，（ ）属于稳定排序算法。

这题考排序算法的稳定性，拿到题先想‘相等元素的相对顺序变没变’，用这个定义去筛选项，别被时间复杂度带偏。

很多同学习惯把冒泡和选择排序混为一谈，觉得它们都是‘慢’的就不分彼此，其实选择排序是典型不稳定排序，它每次选最小值放到前面，一旦有相等元素，后面的那个会被提前覆盖，顺序就乱了；还有人误以为冒泡排序因为交换少就稳定，这没错，但容易忽略它只交换相邻元素，相等时不交换，所以稳定。

这道题考查排序算法的稳定性，核心就是看相等元素的相对顺序在排序后是否保持不变。命题人喜欢用‘冒泡、选择、快速、堆’这些经典算法做干扰项，测试你对稳定性的直觉判断，而不是死记硬背时间复杂度。稳定排序包括冒泡、插入、归并、计数、基数等；不稳定排序则有选择、快速、希尔、堆排序等。拿到题先想‘相等元素的相对顺序变没变’，用这个定义去筛选项，别被时间复杂度带偏。比如选择排序，无论怎么优化，它都是每次从剩余序列里挑最小值放到前面，一旦有相等元素，后面的那个会被提前覆盖，顺序就乱了，所以它肯定不稳定；快速排序因为分区时左右子序列的相对位置会打乱，也是不稳定；堆排序同理，从堆顶弹出最小值后，堆结构重组会改变相等元素的相对顺序。只有冒泡排序，它只交换相邻元素，相等时不交换，所以稳定。计数排序和基数排序虽然稳定，但题目没给，而且它们不是比较排序，命题人常在这里挖坑。解题技巧就是熟记常见排序算法的稳定性，遇到新算法先想它是否涉及‘相等元素交换’或‘分区打乱’。考频方面，BCSP-X 2024 第 14 题是纯概念单选题，这类题在 BCSP 中属于高频考点，近五年至少考了 3 次，主要集中在第 10-15 题区间，命题趋势是越来越喜欢把稳定性与时间复杂度混在一起考，比如问‘哪种排序既稳定又 O(n log n)’，或者‘哪种排序在相等元素很多时表现最好’，不过暂无足够依据预测具体题目形式。避坑指南：计数排序不是比较排序，是桶排序思想，别把它当成‘冒泡的升级版’；选择排序比较次数始终为 n(n-1)/2，与初始状态无关，这是它不稳定的根本原因。总之，这题正确答案就是 C，冒泡排序。