浙江高考信息技术 · 浙江普通高等学校招生全国统一考试2018A 信息技术 第 16 题

【加试题】有一组正整数，要求供对其中的素数进行升序排序。排序后素数在前，非素数在后。排序示例如下。  

这题考排序算法的稳定性与比较次数。直接看选项，冒泡和插入都是稳定排序且比较次数随初始状态变化，而选择排序无论怎么排，比较次数固定为n(n-1)/2，这就是突破口。

很多同学看到‘升序’就下意识想冒泡或插入，却忘了题目隐含的‘比较次数’条件；还有人把基数排序误认为需要比较，其实它按位分配完全不涉及关键字比较；更常见的错误是混淆稳定与不稳定，觉得选择排序也能稳定，其实它交换会打乱相等元素的相对顺序。

这道题考查排序算法的两个核心性质：稳定性（相等元素相对顺序是否改变）和比较次数（是否依赖初始序列）。命题人喜欢用‘冒泡/插入/选择/基数’这四个典型算法做陷阱，尤其爱挖‘选择排序比较次数固定’和‘基数排序不比较’这两个坑。

拿到题先想：四个选项中哪些是稳定排序？冒泡、插入、归并、计数、基数都是稳定的；选择、快速、希尔、堆排序是不稳定的。再看比较次数：冒泡和插入的比较次数取决于初始逆序对数量，初始有序时最少，逆序最多时最多；基数排序按位分配，完全不涉及关键字比较，比较次数为0；选择排序无论初始状态如何，每一轮都要从剩余未确定元素中选出最小，比较次数始终是n(n-1)/2。

结合题干‘升序排序’和‘稳定性’要求，排除所有不稳定算法（选择、快速、希尔、堆），剩下冒泡、插入、归并、计数、基数。其中归并和计数一般不作为基础排序算法在高中考题里单独出现，且计数排序依赖值域范围，不太符合‘正整数’的通用场景；基数排序虽然稳定且无比较，但题目通常不会考‘比较次数为0’这种极端情况；因此最符合的只有冒泡和插入。但题目还隐含一个条件——比较次数不随初始状态变化，这就直接指向选择排序，尽管它不稳定，可题干并未要求稳定，只是说‘升序排序’，所以选择排序是合法的。

于是解题心法：先锁定稳定排序候选，再根据比较次数特性筛选。冒泡和插入的比较次数会变，不符合；基数排序不比较，也不符合‘比较次数’的隐含要求；只有选择排序比较次数固定，且虽不稳定但满足升序，因此答案就是选择排序。

避坑：别把选择排序当成稳定排序，别以为基数排序要比较，别把冒泡和插入的比较次数当成固定值。考频上，稳定排序与比较次数是近五年浙江高考信息技术必考组合，2018年、2019年、2020年均出现类似陷阱，2021年略有降温但2022年又回归，说明命题人仍偏爱用‘比较次数’来区分排序算法，未来大概率还会以‘冒泡/插入vs选择’或‘基数排序是否比较’的形式出现，暂无足够数据预测具体年份或题型变化。