搜索

为什么introsort(内省排序)里用堆排序而不是希尔?

gecimao 发表于 2019-05-25 17:10 | 查看: | 回复:

  STL:sort 貌似也是introsort,虽然时间复杂度比不过堆排序,但希尔排序实际效率不是比堆排序好点吗,难道是处理大数据时的实际效率比不过堆排序?

  可选中1个或多个下面的关键词,搜索相关资料。也可直接点“搜索资料”搜索整个问题。

  既然时间复杂度比不过堆排序,那么为什么能得出实际效率比堆排序好的结论呢?希尔排序时间复杂度介于O(nlogn)到O(n^2)之间,要在比较理想的情况下才能达到和堆排序一样的O(nlogn),这时由于算法中的一些常数因素会使得希尔排序更快,但毕竟大部分情况下希尔排序是达不到这样的复杂度的吧,那么由复杂度差距+数据量带来的效率差距就不是常数因素可比的了。如果数据量小的话那直接用简单插入排序就好了,也不需要用希尔排序。

本文链接:http://baumseelen.com/duipaixu/470.html
随机为您推荐歌词

联系我们 | 关于我们 | 网友投稿 | 版权声明 | 广告服务 | 站点统计 | 网站地图

版权声明:本站资源均来自互联网,如果侵犯了您的权益请与我们联系,我们将在24小时内删除。

Copyright @ 2012-2013 织梦猫 版权所有  Powered by Dedecms 5.7
渝ICP备10013703号  

回顶部