对同一待排序序列分别进行折半插入排序和直接插入排序，两者之间可能的不同之处是______。
A. 排序的总趟数
B. 元素的移动次数
C. 使用辅助空间的数量
D. 元素之间的比较次数
[解析]折半插入排序所需附加存储空间和直接插入排序相同, 从时间上比较,折半插入排
序仅减少了关键字间的比较次数,而记录的移动次数不变。折半插入排序的时间复杂度仍为 (n2), 所以两者之间的不同只可能是元素之间的比较次数。
题目里出现了一个新概念，折半插入排...
用户登录可进行刷题及查看答案
题目里出现了一个新概念，折半插入排序，本质还是插入排序，遵守插入排序的规则。
折半插入排序插入元素时采用的是折半查找的方式，直接插入排序插入元素时采用的是顺序查找的方式。
折半查找的时间复杂度为 O(logn) ，顺序查找的时间复杂度是 O(n) ，都是基于比较的查找算法。
折半插入排序和直接插入排序元素之间的比较次数可能不同。
插入排序的排序的总趟数、元素的移动次数取决于待排序序列。
插入排序使用辅助空间的数量恒为 O(1) 。
本题选D。
The road of your choice, you have to go on !
粤ICP备16082171号-1
登录后提交答案