NOIP 提高组初赛 · NOIP 2010 提高组初赛试题 第 13 题

原地排序是指在排序过程中（除了存储待排序元素以外的）辅助空间的大小与数据规模无关的排序算法。以下属于原地排序的有(   )。

这题考查原地排序的概念，拿到题先想：辅助空间是否随数据规模增长。冒泡、插入、选择都只用常数个临时变量，基数排序需要计数数组，所以选ABD。

学生容易把基数排序当成原地，因为它不交换大量元素，但命题人特意挖了这个坑——基数排序依赖计数数组，空间复杂度是O(k)，与数据规模无关但与基数k有关，不符合原地排序定义。

原地排序是指在排序过程中，除了存储待排序元素本身之外，所需的辅助空间大小与数据规模无关，即辅助空间复杂度为O(1)。命题人考这个概念，往往不是为了让你背定义，而是让你在四个看似都“不移动大量数据”的排序算法里，精准识别出那个偷偷用了额外数组的。常见的坑就是基数排序：它通过计数数组统计频次，空间占用与基数k相关，显然不属于原地排序。因此，本题正确选项是A、B、D。

冒泡排序：只需一个临时变量用于交换相邻元素，空间O(1)。 插入排序：同样只需用一个临时变量暂存当前元素，空间O(1)。 选择排序：只需一个临时变量暂存最小值，空间O(1)。 基数排序：需要计数数组（长度等于基数k），空间O(k)，不符合原地排序定义。

考频趋势：排序基础是高频考点，题库共考过249题，覆盖9个考试级别。从逐年分布看，2023-2026年考题数量激增（2023年22题、2024年51题、2025年57题、2026年50题），说明命题人正加大对此类概念辨析的考查力度。分赛事来看，GESP五级74题、CSP入门级44题、NOIP提高组初赛12题，原地排序这类概念题在NOIP提高组初赛中出现频率不高，但近年趋势显示，初赛越来越偏向细节辨析，未来更可能以“概念陷阱”形式出现，例如把基数排序、桶排序等混入原地排序选项，或问“哪种排序在极端情况下需要O(n)额外空间”。暂无足够依据预测具体年份或题型，但建议重点复习原地排序与非原地排序的边界案例。