题目

下列排序算法中，最坏情况下元素移动最少的是( )。

错因

A

冒泡排序最坏情况（逆序输入）下，每对相邻元素都要交换一次，总交换次数 ，每次交换 = 3 次移动，总移动数 ——是四个选项中"移动"最多的之一。

B

直接插入排序最坏情况（逆序输入）下，每个新元素都要从已排序段尾部一直往前移动到首部，所有后续元素也跟着后移。总移动量 。注意"移动"包含元素整体后移，不仅是交换。

C

快速排序虽然平均时间 ，但最坏情况退化为 （例如已排序输入选首元素为枢轴）。最坏移动次数同样是 ，混淆"平均"和"最坏"是常见陷阱。

总解析

思路：四种算法在最坏情况下的元素移动量级如下：

排序算法	最坏比较次数	最坏移动次数
冒泡排序
直接插入排序
快速排序
简单选择排序

为什么简单选择排序移动最少：

简单选择排序每一趟（共 趟）：

1. 在剩余未排序部分遍历找出最小值（只比较，不移动）；
2. 把最小值与当前位置交换（至多 1 次交换 = 3 次移动）。

总移动次数 ，与输入是否逆序无关。

关键直觉：选择排序是"用比较替代移动"——遍历过程不动数据，等找到目标后只做一次集中交换；其它三种算法在比较过程中就伴随移动，因而被推到 。

最终答案是 D。