1回答

liuyubobobo

2017-08-17

已采纳

非常好的问题。我认为虽然可以但是不实用。

在插入排序中插入二分法虽然能够在O(logN)的时间内找到待插入的位置但是之后真正的将元素插入到这个位置还是需要不断后移元素使用O(N)的时间。整体插入排序算法的时间复杂度依然是O(N^2)的级别。虽然理论上比不使用二分查找的插入排序会快一些但由于复杂度没有改变本质变化不大。O(N^2)级别的排序算法在数据量大的情况下就是没有用武之地。不过你可以实现一个使用二分法的插入排序亲自测试一下会快多少相信是个不错的练习

不过更糟糕的是如果通过二分查找法寻找待插入的位置插入排序算法在数组近乎有序的情况下会“进化”成O(N)的算法这一特性也没有了想想看为什么同时由于二分查找代码中固有的复杂度将使得我们在这个课程中不断使用的使用插入排序优化小数组的方式也不能使用了依然是可以自己亲自做实验对比一下

所以虽然理论上能够使用二分查找优化插入排序算法但是在实践中很少有人会这么做

1

3

liuyubobobo

回复

谢脉

是。因为其本质依然是O(n^2)的算法：）

2017-08-18

共3条回复