判断题
偏易
#17132
对 5 个不同的数据元素进行直接插入排序,最多需要比较 10 次就可完成。
对 5 个不同的数据元素进行直接插入排序,最多需要比较 10 次就可完成。
答案与解析
正确答案:对
解析
分析直接插入排序在最坏情况下的比较次数。插入排序每轮将一个元素插入已排序部分,比较次数取决于该元素在已排序序列中的插入位置。对n个元素,第i轮最多比较i次(i从1到n-1)。累计最多比较次数为1+2+…+(n-1),即n(n-1)/2。代入n=5,计算该表达式的值。考虑是否存在某种初始排列使得比较次数不超过10。比较实际最大值与题干所述上限的关系。