题目

下列排序算法中，元素的移动次数与关键字的初始排列次序无关的是()。

错因

A

直接插入要把待插入元素和有序部分逆序比较 + 后移。初始越接近有序，移动越少：

• 已升序：0 次移动
• 完全逆序：移动次数达

移动次数显然依赖初始排列，不满足"无关"。

B

起泡排序每趟两两比较、逆序就交换。初始越有序、交换越少：

• 已升序：0 次交换
• 完全逆序：交换次数达

交换=移动也强烈依赖初始排列。

D

快速排序每次划分时按 pivot 把元素分到两边，partition 中元素的交换次数与初始排列直接相关：

• 已升序（最坏情况之一）：每个元素都被某次比较涉及，但交换次数较少
• 完全逆序：partition 中交换很多
• 一般情况：交换次数高度依赖具体序列

总移动次数和递归深度都与初始排列有关。

总解析

核心知识点：基数排序的工作原理决定了它对每个元素都做"机械的、固定次数的"分配-收集，与谁大谁小、初始顺序无关。

基数排序的执行（设关键字 d 位、基数 r、n 个元素）：

1. 对最低位（或最高位）开始，按当前位的值把每个元素分配到 r 个桶里。
2. 按桶顺序收集回一个序列。
3. 重复 d 趟。

每个元素在每一趟都被一次分配 + 一次收集——正好移动 2 次（如果用顺序方式实现，从原序列搬到桶、从桶搬回原序列；用链式实现则是指针修改但仍是 次/趟）。

总移动次数恒为 ——只取决于元素个数 n 和位数 d，与各元素的相对大小、初始排列完全无关。

对比表：

排序算法	移动次数	是否依赖初始排列
直接插入	0 ~	是，已序时 0、逆序时最多
折半插入	比较省了，移动仍 0 ~	是（同上）
起泡	0 ~	是
简单选择	至多 次（每趟最多 1 次交换）	基本无关（比较次数固定 ，移动则取决于"是否需要换位"）
希尔	与序列有关	是
快速	与序列有关	是
堆排序	与序列有关	是
归并	，但常数与序列有关	略有
基数		否 ✅

唯一干扰项警示：选择排序的"比较次数"与初始排列无关（永远 ），但移动次数仍依赖初始（例如已序时 0 次交换）。本题问的是"移动次数"——选择排序也不算"无关"。

真正"移动 / 比较 / 时间"全都与初始排列无关的，只有基数排序。

记忆点：基数排序不做"两两比较"，而是按位入桶——它根本不关心元素之间谁大谁小，所以初始排列毫无影响。

最终答案是 C（基数排序）。