题19

题19

题目

Q:【2020 统考真题】对大部分元素已有序的数组排序时, 直接插入排序比简单选择排序效率更高, 其原因是 ( ).
I. 直接插入排序过程中元素之间的比较次数更少
II. 直接插入排序过程中所需的辅助空问更少
III. 直接插入排序过程中元素的移动次数更少
A. 仅 I
B. 仅 III
C. 仅 I、II
D. I、 II 和 III

分析

A:对于已经排序的数组，选择排序会被选择的基准元素重新划分，导致一定程度上失去了已排序的优势
而插入排序，是维护了一个已经排序的序列，然后把未排序序列放进已排序序列中，也就是说，我们要把一个新元素放进已经排序的序列中，如果他比这个已经排序的序列中，最大的一个元素还要大，那么显然就不要对比了，直接放在最后一个位置就好了，这样就减少了比较次数
答案考虑的出发点是，挪动数组使之呈现为有序，归整的这个过程的移动次数

解

A
考虑比较极端的情况,对于有序数组,直接插入排序的比较次数为 ,简单选择排序的比较次数始终为 正确。
两种排序算法的辅助空间都是 ,无差别, II 错误。
初始有序时, 移动次数均为 0 ;
对于通常情况, 直接插入排序每趟插入都需要依次向后挪位, 而简单选择排序只需与找到的最小元素交换位置, 后者的移动次数少很多, III 错误。