首页 > 试题广场 >

要从1000个数据元素中选五个最小的，下面排序算法中，那个算

[单选题]
要从1000个数据元素中选五个最小的，下面排序算法中，那个算法最快？（） 
  • 希尔排序
  • 快速排序
  • 堆排序
  • 简单选择排序
查看答案及解析
添加回答
走位崴了脚头像 走位崴了脚
简单理解，考虑每种算法的解决问题的最坏情况，希尔排序和快速排序最坏情况O(n2)。简单选择排序1000+999+998+997+996=5000-10=4990，优于希尔和快排，堆排序是简单选择排序的优化版，优于简单选择排序。堆排序耗时可参考ChrisZZ的解析。
编辑于 2021-02-28 17:34:17 回复(0)
小公牛呦头像 小公牛呦

   
编辑于 2017-07-17 15:33:50 回复(2)
ChrisZZ头像 ChrisZZ
选择答案C。
按我的理解，D选项，简单选择排序，每轮选出最小的一个元素，那么5轮就完成了任务，比较次数为1000+999+998+997+996=5000-10=4990次。
而C选项，堆排序，首先需要建堆，建堆时间复杂度是O(n)，根据《算法导论》上chap6的公式推导，建堆时间的上界是O(2n)，那么需要2000次比较。接下来依次挑选最小的元素，每次挑选完一个元素，都需要重新调整堆，调整堆的时间复杂度为O(log n)，根据《算法导论》的推导是T(n)<=T(2n/3)+O(1),把n=1024带入，发现对调整时间大约为10次，并且推导中的O(1)时间是用于调整根节点、左儿子、右儿子这3个节点的时间，显然时间开销小于10次，那么5次取最小元素的时间开销就小于5*10*10=500，所以总时间开销不足2500次。                                                                                                                                                                                                                                                                                                  
编辑于 2017-09-08 11:06:42 回复(1)
牛客527161027号头像 牛客527161027号
既然是 1000 个数据，希尔排序和选择排序就先排除了。其次是快速排序和堆排序。快速排序在基本有序的情况下效率比较好，但是这里不知道到底什么情况，快速排序可能会取最差值，所以选堆排序
发表于 2021-08-25 17:09:24 回复(1)
AAS48头像 AAS48
因为只用选最小的5个元素，所以显然只能使用堆排序或选择。明显的，堆排序比选择排序快。
发表于 2021-12-14 18:52:48 回复(0)
大哥给个offer再走啊头像 大哥给个offer再走啊
不知道对不对，按我的理解，使用B选项快速排序的话，平均情况下比较次数：1000+500+250+125+63+32+16+8+4=1998次，因为只需要比较左边小于基准的部分，时间复杂度是在O(n)的。
发表于 2019-07-05 20:36:14 回复(2)
Mr.DoubleU头像 Mr.DoubleU
快排的topk问题能达到On,剑指offer里面说的,这题明显不对
发表于 2018-05-20 13:18:37 回复(8)
梦境迷离头像 梦境迷离
建堆 花费O(N) deletemin花费log(N) 对N个数总共NlogN 
但是数据结构与算法分析上说实际情况比Sedgewick增量序列的希尔排序慢，后者平均O7/6 理论和实践
发表于 2017-12-15 21:01:32 回复(0)
提交观点

问题信息

排序
上传者：阿奻_
难度：
8条回答 6044浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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