题7

题7

题目

数据序列 只能是下列排序算法中的 ( ) 两趟排序后的结果.
A. 快速排序 B. 冒泡排序 C. 选择排序 D. 插入排序

分析

快排因为选择了基准，序列会呈现出，以某个元素为基准，然后左侧的元素都比他小，右侧的元素都比他大
如果是插入排序的逻辑，那么就是从第一个元素开始，逐个比较，然后插入到合适的位置，这使得序列呈现为逐渐有序，也即是从前到后经过多轮以后，肯定是有序的

解

A
若为插入排序, 则前三个元素应该是有序的, 显然不对。而冒泡排序和选择排序经过两趟排序后应该有两个元素处于最终位置 (最左/右端), 无论是按从小到大还是从大到小排序, 数据序列中都没有两个满足这样的条件的元素, 因此只可能选 A 项。
【另解】先写出排好序的序列, 并和题中的序列做对比。
题中序列:
已排好序序列:
在已排好序的序列中, 与题中序列相同的元素有 4、8 和 20 , 最左和最右两个元素与题中的序列不同, 所以不可能是冒泡排序、选择排序或插入排序。