老师，能否可以在数据量极大的情况下在插入排序中添加二分法？

Answer 1

liuyubobobo 2017-08-17 02:51:33

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

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

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

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

• 提问者 谢脉 #1

  非常感谢！

• 提问者 谢脉 #2

  那么您的意思是可以加快搜索的速度但是不能加快数字移动的速度，所以性能还是比快排等O(N*logN)级别的排序方法慢。是吗？

• liuyubobobo 回复 提问者 谢脉 #3

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