首页 > 试题广场 >

下面哪种排序的平均比较次数最少（）

[单选题]
下面哪种排序的平均比较次数最少（） 
  • 插入排序
  • 选择排序
  • 堆排序
  • 快速排序
添加回答
推荐
Pandora头像 Pandora
上图。虽然平均情况下快排和堆排时间复杂度都为O(nlogn)，甚至堆排序的最坏情况下时间复杂度和辅助空间都优于快排。但是不能否认的是，虽然都是O(nlogn)级别，但是快排的常数因子要小于堆排序。实验可验。
编辑于 2016-03-13 01:13:38 回复(14)
CodeMan头像 CodeMan
肯定是D啊！ 
因为堆排序需要构建堆，所以比较次数是要多于快速排序的！
发表于 2016-03-17 22:09:50 回复(0)
我是超越迷妹了😘头像 我是超越迷妹了😘
发表于 2017-10-09 08:57:07 回复(2)
细雨湿身头像 细雨湿身
快排平均：T(n)=2T(n/2)+n  ==>> T(n)=nlog(n)      堆排序平均：每次下滤，两个儿子比较，然后与父亲比较，因为一般下滤logn层，每次共比较2logn，所以n*2logn
发表于 2016-10-09 15:43:33 回复(3)
ZeroCBoy头像 ZeroCBoy
我是这样理解的：  快排平均：T(n)=2T(n/2)+n  ==>> T(n)=nlog(n)      堆排序平均：每次下滤，两个儿子比较，然后与父亲比较，因为一般下滤logn层，每次共比较2logn，所以n*2logn     这里说的是大概，在这里上下浮动~~
发表于 2016-08-26 15:58:03 回复(1)
平林新袖头像 平林新袖
求指教为什么不是堆？
发表于 2015-09-17 14:42:28 回复(3)
nyhk头像 nyhk
快排和堆排都是O（nlogn）级别，但快排的平均比较次数大概是1.39nlogn，而堆排序大概是2nlogn，所以快排的更少
发表于 2016-09-18 10:19:57 回复(0)
rppp头像 rppp
堆排序：包括建初堆和堆排序，平均比较次数多于快速排序
发表于 2017-08-08 23:58:55 回复(0)
刘大庆_头像 刘大庆_
建初堆
发表于 2021-07-16 09:14:15 回复(0)
Camlo15头像 Camlo15
难道我还要一个个比给你看吗？
发表于 2018-07-12 14:23:34 回复(0)
黏黏糖头像 黏黏糖
快排的常数因子要小于堆排序，堆排序 2nlgn 快速1.39nlgn
编辑于 2017-06-23 17:05:21 回复(0)
被支配的恐惧头像 被支配的恐惧
因为堆排序需要构建堆，所以比较次数是要多于快速排序的！
发表于 2017-04-12 21:12:17 回复(0)
尼见头像 尼见
综合来说，快排算是综合性能最好的内部排序算法了。
发表于 2016-06-08 20:49:32 回复(0)
岚风月头像 岚风月
尽管快速排序的最坏时间为O(n2 )，但就平均性能而言，它是基于关键字比较的内部排序算法中速度最快者，快速排序亦因此而得名。它的平均时间复杂度为O(nlgn)。应该选D吧
发表于 2015-09-19 13:56:14 回复(0)
提交观点

问题信息

排序
来自：凤凰网2015校园招聘...
难度：
14条回答 16441浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号