我也会受到宇宙射线的冲击吗？
本文起稿于自己淡役一年后，练初赛时遇到这道题：
然后被气笑了。
1 宇宙射线是什么
百度百科介绍：
宇宙射线，是来自外太空的带电高能次原子粒子。它们可能会产生二次粒子穿透地球的大气层和表面。射线这个名词源自于曾被认为是电磁辐射的历史。主要的初级宇宙射线（来自深太空与大气层撞击的粒子）成分在地球上一般都是稳定的粒子，像是质子、原子核、或电子。但是，有非常少的比例是稳定的反物质粒子，像是正电子或反质子，这剩余的小部分是研究的活跃领域。
简单来说，就是一种原子粒子，能穿透地球大气层并产生次级粒子簇射。
2 它对我们产生什么影响
- 对我们：DNA 损伤，生育能力下降，基因突变。
- 对电子设备：缩短设备的使用寿命，甚至导致数据丢失，破坏，改变。所以我们运气只要足够好，就可以把自己的 NOI 分数合理地变为
700 分了。 - 对环境：臭氧层破坏，气候变化。
- 对信息学：初赛题目又增加了一类题。
3 如何避免宇宙射线的冲击
回到上面这道题，本题做题的关键是：
基数排序是稳定的，相同键值的元素在排序后相对顺序不变。
题目中受影响的元素只有一个，而其他所有元素的相对顺序在排序过程中永远不会被破坏。
因此基数排序结束后，整个序列是“异变后的值”排好序的。我们把这个“异变的值”从序列中剔除，剩下的元素恰好是按照它们原本正确的值排列好的，所以必然是一个完全有序序列。
那我们如何解决这类题喵？
其实，“三步看”策略即可喵：
- 看稳定：是稳定排序（归排、冒排、插排、基排）还是不稳定排序（快排、选排、堆排）？
- 若稳定，其他元素相对位置不变，有概率 完全。
- 若不稳定，大概率 无序。
- 看时机：是在处理前，还是在处理中？
- 若发生在处理之后，如计数排序的频次数组已生成，那么直接受到重大冲击，必定 乱。
- 若发生在逐轮处理中，只要算法依赖前一轮结果，异变元素只会被挤到队首或队尾，移除后剩余依然 有序。
- 看结构：如果排序涉及 堆 等结构，异变后父子关系错乱，就会导致上面题目中最猎奇的答案 —— 两个有序子序列。或者说 无序。
为加深理解，下面给出几道题：
:::info[例题 1]
某计数排序算法预设数据范围为 [0, 100]。程序先遍历一遍数组，统计出每个值的出现次数存入 cnt 数组。统计完成后，在准备输出结果时，某个值为 50 的元素因宇宙射线突变为 150（超出范围，程序忽略溢出，将其当作最大值 100 输出）。排序结束后，若移除这个突变元素，剩余序列最可能的情况是（）。
A. 完全有序\ B. 前后两个有序子序列\ C. 一个有序子序列和一个基本无序的子序列\ D. 基本无序 :::
:::success[解析 1]
- 计数排序在输出阶段依赖预先固定好的
cnt频次数组，此时频次表已锁死，不再关心元素当前真实值，此乃一失。 - 受影响元素只有一个，其他元素的值和数量都没变，此乃二判。
- 异变元素仍按照旧
cnt数组被强行放到值为50的桶位输出，导致从50号位置起，后续所有元素整体向后错位一位。即使移除这个突变元素，错位引起的乱序依然残留，无法复原为有序，此乃三定。
综上，剩余序列基本无序，选 D。 :::
:::info[例题 2] 在对序列进行二路归并排序的合并阶段，某个元素的值因射线突变为一个极大的数，并随即被合并到当前子序列的末尾。整个排序结束后，若移除该突变元素，则剩余序列（ ）。
A. 完全有序\ B. 前后两个有序子序列\ C. 一个有序子序列和一个基本无序的子序列\ D. 基本无序 :::
:::success[解析 2]
- 归并排序是稳定排序，每一轮合并只依赖相邻子序列的两两比较，且不依赖任何预统计信息，此乃一胜。
- 受影响元素只有一个，其他元素之间的比较顺序和合并路径从未被干扰，此乃二胜。
- 突变元素仅在合并时被当作大值追加到当前子序列的末尾，从未影响其他元素的相对有序关系。移除它后，剩下的元素恰好就是原本正确的归并排序结果。
综上，还是有序序列，选 A。 :::
:::info[题目 3] 在快速排序的分区过程中，一个未被选为基准的元素因宇宙射线异变为一个极小值。由于分区交换，这个异变元素被交换到了基准的左侧，同时将原本左侧的某个元素挤到了右侧。排序结束后，若移除该异变变元素，则剩余序列最可能是（ ）。
A. 完全有序\ B. 前后两个有序子序列\ C. 一个有序子序列和一个基本无序的子序列\ D. 基本无序 :::
:::success[解析 3]
- 快速排序是不稳定排序，分区过程中的交换操作会剧烈改变元素的原始相对位置，此乃一失。
- 受影响元素只有一个，但因为它突变为极小值，会作为“干扰锚点”参与后续交换，导致原本左侧的一个正常元素被硬生生挤到右侧区域，此乃二变。
- 排序结束后，突变元素被安置在最左侧。移除它后，左侧缺失了一个本该属于这里的小元素（导致左侧缺位），右侧却多了一个不该存在的“外来小元素”（导致右侧混入异类）。最终呈现左侧基本有序，右侧因混入异类而基本无序，此乃三定。
综上，是一个有序子序列和一个基本无序的子序列，选 C。 :::
4 我不想思考了，有什么办法快速解题
其实，如果我们注意力足够好，就可以发现一个一般性结论：
- 若是 基数排序 或 稳定排序，则一般 完全有序。
- 若 统计完频次后突变，则一般 完全无序。
- 若 堆排序 或 快速排序，则一般 前后两个有序子序列 或一个有序，一个无序。
5
本文经 Deepseek-V4 润色，所以可能有些话有一点 AI 味？