408考研逐题详解：2010年第11题——常见排序方法-拓冰建站

2010年第11题

对一组数据（2，12，16，88，5，10）进行排序，若前三趟排序结果如下：

第一趟排序结果：2，12，16，5，10，88

第二趟排序结果：2，12，5，10，16，88

第三趟排序结果：2，5，10，12，16，88

则采用的排序方法可能是（）

A.冒泡排序 B.希尔排序

C.归并排序 D.基数排序

解析

本题考查的核心知识点是排序算法的原理和过程，特别是不同排序算法在中间步骤（趟）中表现出的特征。题目选项中涉及的四种排序算法：

冒泡排序：
- 原理：通过重复遍历列表，比较相邻元素，如果顺序错误（例如前大后小）则交换它们。每趟排序会将一个最大（或最小）元素“冒泡”到其最终位置。
- 趟的特征：每趟排序后，未排序部分的最大元素会移动到正确位置（例如升序时移到末尾）。交换只发生在相邻元素之间，排序过程稳定（相等元素的相对位置不变）。
- 时间复杂度：平均和最坏情况为 $O(n^2)$ ，最好情况（已有序）为 $O (n)$ 。
- 适用场景：小规模数据或部分有序数据。
希尔排序：
- 原理：基于插入排序的改进，通过定义增量序列（如 $\ldots$ ）将数据分成多个子序列，对每个子序列进行插入排序。随着增量减小，子序列逐渐变长，最终增量为1时整体排序。
- 趟的特征：每趟对应一个增量，排序后数据在“宏观”上部分有序（子序列内有序）。元素可能跨越多个位置移动，非相邻交换。中间结果不保证最大/小元素在末尾。
- 时间复杂度：依赖于增量序列，平均为 $\log n)$ 到 $O(n^2)$ 。
- 适用场景：中等规模数据，比简单插入排序高效。
归并排序：
- 原理：分治法策略，将列表递归分成两半，分别排序后合并。合并过程比较两个有序子序列，生成新有序序列。
- 趟的特征：在自底向上实现中，每趟合并相邻的子序列（长度从1开始倍增）。中间结果表现为局部有序的子段（如长度2、4的有序块），但整体可能无序。元素位置变化大，但无显式交换过程。
- 时间复杂度：平均和最坏情况为 $\log n)$ 。
- 适用场景：大规模数据，需要稳定排序。
基数排序：
- 原理：非比较排序，根据键值的位数（如个位、十位）分配和收集元素。通常使用桶（bucket）实现，从最低位（LSD）或最高位（MSD）开始排序。
- 趟的特征：每趟处理一位数字，进行分配（入桶）和收集（出桶）。每趟后，数据按当前位有序，但整体无序。元素可能移动到任意位置，非相邻操作。要求数据为整数或字符串。
- 时间复杂度： $\cdot n)$ ，其中 $d$ 为位数。
- 适用场景：整数或字符串排序，位数较小。

结合知识点分析本题，已知数据：初始序列（2, 12, 16, 88, 5, 10），前三趟结果：

第一趟：2, 12, 16, 5, 10, 88
第二趟：2, 12, 5, 10, 16, 88
第三趟：2, 5, 10, 12, 16, 88（已有序）

从每趟的结果中可以观察到：

最大元素逐步“沉底”：第一趟后，最大值 88 移至末尾；第二趟后，次大值 16 移至倒数第二位置；第三趟后完全有序。这符合冒泡排序的特征——每趟确保一个最大元素就位。
变化发生在相邻元素交换（如第二趟中 16 和 5、16 和 10 的交换），而非跳跃移动。这与冒泡排序的相邻比较交换一致。

再者，还可以对选项中的其他算法进行排除：

希尔排序：基于增量分子序列排序。例如，6 个元素若增量=3，子序列应为（2,88）、（12,5）、（16,10），排序后可能为（2,88）、（5,12）、（10,16），但结果序列（如 2,5,10,88,12,16）与题目第一趟（2,12,16,5,10,88）不符。元素移动非相邻，题目中无增量分组痕迹。
归并排序：分治合并过程。第一趟通常合并相邻对（如（2,12）、（16,88）、（5,10）），结果应为局部有序块（2,12,16,88,5,10），但题目第一趟中88在末尾、5和10移动，不符合合并特征（合并后子序列有序但整体无序，且无元素远距离移动）。
基数排序：按位分配收集。例如，按个位排序：个位值（2,2,6,8,5,0）→ 桶收集后序列可能为（10,2,12,5,16,88），与题目第一趟（2,12,16,5,10,88）不符。题目中无按位处理迹象（如5和10未按位分组）。

因此，符合题目要求的应该是“冒泡排序”。

本题答案：A