算法分析 折半搜索比顺序搜索查找快,所以折半插入 排序就平均性能来说比直接插入排序要快。 它所需的排序码比较次数与待排序对象序 列的初始排列无关仅依赖于对泉个数。在 插入第i个对象时需要经过Logi+1次排 序码比较,才能确定它应插入的位置。因此 将n个对象为推导方便设为n=k)用折半 插入排序所进行的排序码比较次数为: ∑(g2]+1)≈nlog2n◼ 折半搜索比顺序搜索查找快, 所以折半插入 排序就平均性能来说比直接插入排序要快。 ◼ 它所需的排序码比较次数与待排序对象序 列的初始排列无关, 仅依赖于对象个数。在 插入第 i 个对象时, 需要经过 log2 i +1 次排 序码比较, 才能确定它应插入的位置。因此, 将 n 个对象(为推导方便, 设为 n=2k )用折半 插入排序所进行的排序码比较次数为： (   ) − = +   1 1 2 2 log 1 log n i i n n 算法分析