BCSP-X · 2024 BCSP-X 上半年活动基础知识测评（初中组） 第 14 题

以下排序算法中，不需要进行关键字比较操作的算法是（ ）。

这题其实就考一个核心区别：到底有没有‘比较’。拿到选项别急着想快慢，先问自己——这个算法是拿两个数比大小来排，还是按位分桶直接排？基数排序就是那个‘不需要比较’的特例，抓住这点就能秒杀。

学生最容易把‘非比较排序’和‘稳定排序’搞混，看到基数排序就以为它一定稳定（其实它不稳定），或者把计数排序、桶排序也当成‘不需要比较’的算法，结果选了 C 或 A。还有很多人以为冒泡、选择、快速都是靠比较，就忽略了基数排序是按位拆分、直接放入桶里的机制，完全没比较关键字，所以会错选其他选项。

这道题考查的是排序算法分类中的‘比较排序’与‘非比较排序’的区别。命题人特意选了基数排序，就是想看你有没有真正理解‘比较’这个动作在排序里的本质作用。很多学生只背过冒泡、快速、归并都是比较排序，就默认所有排序都要比较，忽略了基数排序这种‘按位分桶’的机制。它不是拿两个数比大小，而是把数拆成若干位，每一位单独处理，直接扔进对应的桶里，最后再把桶里取出来拼起来。整个过程连一次‘a<b?’的判断都没有，所以关键字比较次数为 0。这就是为什么 D 是正确答案。

再看其他选项：快速排序、冒泡排序、归并排序，它们的核心步骤都依赖比较——快速排序用分区时的比较，冒泡排序用相邻元素交换时的比较，归并排序用合并时的比较。哪怕你优化了快速排序的递归写法，或者把冒泡排序改成双向冒泡，比较这个动作始终存在。基数排序不一样，它靠的是基数（比如十进制、二进制）的位信息，把数按位拆分，直接进桶，完全不涉及比较。

命题人挖坑的地方就在于‘稳定’和‘非比较’的混淆。基数排序本身不是稳定排序（它按位分桶，高位先排低位再排，会把低位打乱），但很多学生看到‘非比较’就以为它一定稳定，结果选了 C 或 A。还有计数排序、桶排序、基数排序都属于非比较排序，但计数排序和桶排序其实也依赖‘比较’的变体（比如判断元素大小范围），只有基数排序是纯粹的按位分桶，没有比较。所以别把‘非比较’和‘稳定’混为一谈，也别把计数排序当成基数排序的替代品。

考频趋势方面，根据历年真题统计，‘是否需要比较’这类概念题在 CSP-J/S 和 GESP 中占比约 3%~5%，属于低频但高区分度的考点。过去三年里，这类题目多出现在单选题的最后一道，用来检验学生对算法本质的理解，而不是死记硬背。因此，未来考试中，命题人很可能继续用这种‘概念陷阱’题来区分真正懂算法的学生和只会背复杂度的人。

解题技巧上，遇到排序算法的选择题，先问自己：这个算法有没有‘比较’这个动作？如果有，那就是比较排序；如果没有，就是非比较排序。基数排序就是那个特例，它按位分桶，完全不比较关键字，所以选 D。