题目

若数据元素序列 11，12，13，7，8，9，23，4，5 是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是（）。

错因

A

冒泡排序第一趟就会把最大值 23 冒到末尾，同时 7、8、9 等位置的元素已经被交换移动，第一趟结果就不是 11,12,13,7,8,9,23,4,5，选 A 是没有实际模拟冒泡的第一趟。

C

选择排序第一趟从全部元素中找最小值 4，将 4 换到第 1 位，结果是 4,12,13,7,8,9,23,11,5。第二趟找剩余最小值 5 换到第 2 位，结果是 4,5,13,7,...。与题目序列完全不同，选 C 是没有模拟。

D

二路归并第一趟将相邻的两两元素归并成有序对：(11,12),(7,13),(8,9),(4,23),(5)，结果是 11,12,7,13,8,9,4,23,5。第二趟再合并四元组，结果更不同。选 D 是认为归并也能保持前段有序。

总解析

原始序列：11, 12, 13, 7, 8, 9, 23, 4, 5

直插排序：第 i 趟将第 i+1 个元素插入前 i 个已排好的元素中。

• 第 1 趟：将 12 插入已排序的 [11]。12 > 11，位置不变 → 11, 12, 13, 7, 8, 9, 23, 4, 5
• 第 2 趟：将 13 插入已排序的 [11,12]。13 > 12 > 11，位置不变 → 11, 12, 13, 7, 8, 9, 23, 4, 5 ✓

由于原序列前三个元素 11<12<13 已经有序，插入排序前两趟不产生任何移动，结果与原序列完全相同，与题目吻合。

其他三种排序的第二趟结果均与题目序列不符。答案 B。