题13

题13

题目

Q:【2009 统考真题】若数据元素序列 是采用下列排序算法之一得到的第二趟排序后的结果，则该排序算法只能是 ( ).
A. 冒泡排序
B. 插入排序
C. 选择排序
D. 二路归并排序

分析

A:如果是冒泡排序，跑完了一趟，肯定有元素在正确的位置
如果是插入排序，因为是和一个有序序列比较，把一个无需队列中的元素，插入到有序的部分中，使之有序了，也就是处于正确的位置上
如果是选择排序，因为有一个基准，把序列分为两部分，那个基准元素就是正确的位置，而分割的子序列又会执行这个子任务，导致它的基准又是有序的
经过两趟排序，序列的前三个元素应该是有序的。
观察题中序列，前三个元素
11，12，13确实是有序的，符合插入排序的特点

解

B
每趟冒泡和选择排序后,总会有一个元素被放置在最终位置上。显然,这里 和 所处的位置并不是最终位置, 因此不可能是冒泡和选择排序。二路归并算法经过第二趟后应该是每 4 个元素有序的,但 并非有序,因此也不可能是二路归并排序。