NOIP 普及组初赛 · NOIP 2018 普及组初赛试题 第 8 题

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

这题考非比较排序，直接看选项里哪个不用比大小就行。基数排序把数拆开按位分桶，全程只判断数字是否相等，不比较大小，所以选A。

学生常把‘稳定性’和‘是否比较大小’搞混。冒泡、插入、归并都是稳定的比较排序；基数、计数、桶排序是稳定的非比较排序；快排、堆、选择是不稳定的比较排序。做题时别被‘稳定’两个字带偏，题目问的是要不要比较关键字大小。

这道题考查排序算法的分类，核心是区分‘比较排序’和‘非比较排序’。比较排序靠比大小决定顺序，非比较排序利用数值特性（如位数、出现次数）直接分配，全程不比较谁大谁小。命题人爱挖坑的地方就是混淆‘稳定性’与‘是否比较大小’，还有把基数排序当成普通排序去分析复杂度。拿到题先想：哪些算法不用比大小？答案只有基数、计数、桶排序。再排除其他：冒泡相邻比、堆父子比、插入找位置都要比，所以只有基数排序符合。计算上基数排序只需判断每一位数字是否相等，时间复杂度O(d·n)，d为位数，属于非比较排序的典型代表。避坑提醒：别被‘稳定’误导，基数排序确实是稳定的，但它不是比较排序；而快排不稳定却是比较排序。考频趋势看，排序基础在题库共考过249题，覆盖9个考试级别，2023年22题、2024年51题、2025年57题、2026年50题，近年来高频爆发，尤其2024-2026年合计158题，说明命题人持续深挖排序分类细节。预测未来仍会考非比较排序与其他排序的对比，可能结合计数排序或桶排序出现，但基数排序作为经典非比较排序，大概率继续作为单选考点。暂无足够依据预测具体年份或题型变化，但可确定的是，只要看到‘不需要比较关键字’这类描述，直接锁定基数排序即可。