推广 热搜: 可以  企业  page  百度  搜索引擎    个数  使用  设备  选择 

快速排序、归并排序、堆排序的对比

   日期:2024-12-19     移动:http://ww.kub2b.com/mobile/quote/6689.html

即使是同样的算法,不同的人写的代码,不同的应用场景下执行时间也可能差别很大。下面是一个测试数据:

大数据量下,快速排序优于归并排序优于堆排序。

原因如下:

当数据量越来越大时,

归并排序:比较次数少,速度慢。

快速排序:比较次数多,速度快。

快速排序的优势越来越明显。

原因分析:个人认为是当数据量越来越大时,尽管归并排序的比较次数较少,但是归并排序后期的合并操作所花费的时间便越来越大,合并操作对整体的效率影响越来越明显,包括后面大量数据的赋值操作等。所以当数据量变大时,不需要专门合并的快速排序的优势就变得越发明显。

 

堆排序每次取一个最大值和堆底部的数据交换,重新筛选堆,把堆顶的X调整到位,有很大可能是依旧调整到堆的底部(堆的底部X显然是比较小的数,才会在底部),然后再次和堆顶最大值交换,再调整下来,可以说堆排序做了许多无用功。

总结起来就是,快排的最坏时间虽然复杂度高,但是在统计意义上,这种数据出现的概率极小,而堆排序过程里的交换跟快排过程里的交换虽然都是常量时间,但是常量时间差很多。

 

归并排序和快速排序比较

本文地址:http://ww.kub2b.com/quote/6689.html     企库往 http://ww.kub2b.com/ ,  查看更多

特别提示:本信息由相关用户自行提供,真实性未证实,仅供参考。请谨慎采用,风险自负。


0相关评论
相关最新动态
推荐最新动态
点击排行
网站首页  |  关于我们  |  联系方式  |  使用协议  |  版权隐私  |  网站地图  |  排名推广  |  广告服务  |  积分换礼  |  网站留言  |  RSS订阅  |  违规举报  |  鄂ICP备2020018471号