🏷️ 知识点：直接插入排序

对大部分元素已有序的数组进行排序时，直接插入排序比简单选择排序效率更高，其原因是（ ）。

I. 直接插入排序过程中元素之间的比较次数更少

II. 直接插入排序过程中所需要的辅助空间更少

III. 直接插入排序过程中元素的移动次数更少

排序算法 插入排序

A. 仅 I B. 仅 III C. 仅 I，II D. 仅 I，II 和 III

[tag_link]

正确答案：A

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