CSP-S 提高级 · CSP 2022 提高级第一轮 第 5 题

假设在基数排序过程中，受宇宙射线的影响，某项数据异变为一个完全不同的值。请问排 序算法结束后，可能出现的最坏情况是（ ）。

这题考的是基数排序的稳定性。拿到题先别想具体数字，直接抓住“稳定性”这个核心：基数排序每轮都是稳定分配，其他数据的相对顺序绝不会被一个异常值打乱，移除异常值后剩下的必然有序。

最容易误选 D，觉得一个数变了整个序列就乱了；或者选 C，以为会分成两段。其实基数排序是按位独立分配，异常值只影响它自己，其他人的桶顺序完全没变，所以排除后一定是整体有序的。

考察知识点： 基数排序的原理与稳定性

基数排序按位从低到高进行多轮分配，每轮内部使用的是稳定的计数排序。稳定性意味着：如果两个元素在当前位上的数字相同，它们在上一轮中的相对顺序保持不变。

命题视角： 命题人喜欢用“异变”这种极端情况来测试你对算法稳定性的理解。他们挖坑的地方通常在于让你误以为“一个元素错了，整个排序就崩了”，或者让你觉得异常值会把数组“传染”得乱七八糟。但基数排序的结构决定了它“免疫”这种传播。

思考心法： 拿到题先想“基数排序每轮怎么排？”→“同位数字的元素顺序不变”→“异常值只按自己的新值进桶，不影响别人”→“其他人依然按原顺序出桶”→“移除异常值后，剩下的就是原本就有序的那部分”。

具体怎么算： 假设正常数据经过基数排序后已经有序。某个数据被异变成随机值后：

• 在个位分配时，它按新值入桶，占据了不属它的位置
• 但其他人仍然按自己的个位值入桶，顺序不乱
• 十位、百位同理
• 最终结果中，只有这个异常数据不对，其他人的相对顺序是对的

换种说法：基排序的每一轮就像在图书馆里按字母重新排书——有一本书被换成了另一本的内容，它可能被放到错误的位置，但其他书的顺序不受影响。

避坑： 如果是不稳定的快速排序，一个数变了可能会影响 pivot 选择，导致整体混乱（即选项 D）。但基数排序是按位独立分配，互不干扰，所以选 D 是典型的直觉陷阱。

考频与趋势： 排序基础在题库中是高频考点，共考过 249 题，覆盖 9 个考试级别，逐年分布从 2008 年的 2 题到 2026 年的 50 题，呈现明显上升趋势，尤其在 2024-2026 年单年超过 50 题。计数排序与桶排序作为基数排序的核心子过程，共考过 3 题，覆盖 2 个考试级别（2019-2022），其中 CSP 提高级考了 2 题，CSP 入门级考了 1 题。虽然计数排序单独出题不多，但作为基数排序的组成部分，其稳定性是历年必考的隐性考点。

预测： 基于给定数据，基数排序在 CSP 提高级已考过 9 题，其中 2022 年考了 5 题（含本题），2024 年排序类题目激增到 51 题，计数排序相关题目虽少但基数排序作为综合考点仍会持续出现。预计未来 CSP 提高级和 CSP 入门级仍会考查排序算法的稳定性、异常处理或变种场景（如“某位数字被篡改”、“某轮分配出错”等），但大概率不会再次专门考查计数排序的单独实现细节，因为题库中该细分考点仅 3 题。暂无足够依据预测具体的年份分布，只能判断排序稳定性类题目在近年会保持较高热度。