NOIP 提高 2010 第一轮 第 13 题：原地排序是指在排序过程中（除了存储待排序元素以外的）辅助空间的大小与数据规模

题目

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

答案

A、B、D

题解

考点定位

本题考「原地排序判定（不定项）」,对应大纲 4.1.3 排序（难度【2】）。

解题过程

辅助空间与规模无关的：

• 冒泡 ✓（O(1) 交换缓存）
• 插入 ✓（O(1) 哨兵）
• 基数排序 ✗（需 O(n+k) 辅助数组）
• 选择排序 ✓（O(1)）

答案：A、B、D。

易错提醒

① 原地 = 辅助空间 O(1)；② 归并 O(n)、基数 O(n+k) 都非原地。