对同一待排序序列分别进行折半插入排序和直接插入排序，两者之间可能的不同之处是（ ）。

排序算法

A. 排序的总趟数

B. 元素的移动次数

C. 使用辅助空间的数量

D. 元素之间的比较次数

[tag_link]

正确答案：D

本题考察 插入排序 ，折半插入排序与直接插入排序是将待插入元素插入前面的有序子表，区别是：确定当前记录在前面有序子表中的位置时，直接插入排序是采用顺序查找法，而折半插入排序是采用折半查找法。排序的总趟数取决于元素个数n，两者都是n−1趟。元素的移动次数都取决于初试序列，两者相同。使用辅助空间的数量也都是 O(1)。折半插入排序的比较次数与序列初态无关，为O(nlog2n)：直接插入排序的比较次数与序列初态有关，为O(n)∼O(n2)。