首页 > 试题广场 >

有 1000 个无序的整数，希望使用最快的方式找出前 50

[单选题]
有 1000 个无序的整数，希望使用最快的方式找出前 50 个最大的，最佳的选择是（ ） 
  • 冒泡排序
  • 基数排序
  • 堆排序
  • 快速排序
查看正确选项
添加回答
xncode头像 xncode
【C 】堆排序最优
1、快速排序：在最理想的情况下，即划分可以使得每次分到n/2 的两个序列，复杂度为o（nlogn）。
2、堆排序：无论什么情况都是o（nlogn），当然还有建堆的时间o（n），所以为n+nlogn，但是，本题只是要前五十个，所以堆排序只需要执行50次就够了：n+50logn。
3、本题的条件是1000个无序整数，1000+50log1000<1000log1000，所以自然是堆排序最好。
p.s.：堆排序只需要一个n大小的二叉树就行了，快速排序除了n大小的数组，每次递归最少还得有logn的栈，所以堆排序的空间复杂度也优于快速排序。
发表于 2015-12-14 17:39:54 回复(5)
为你扣下F键头像 为你扣下F键
个人理解：冒泡排序要找出top50，一次遍历找出一个，时间复杂度为O(50n)。 堆排序建初始堆O(n)，找出最大值后，重新建堆O(log)，要找50个，所以总时间复杂度为O(n+50logn)。 而基数排序和快排必须全部排好序，然后取出top50，所以时间复杂度为O(nlogn)。 很明显堆排序最快。
发表于 2018-08-29 16:26:40 回复(1)
牛客185114号头像 牛客185114号
D,快速排序只需要O(N)就能够完成，具体可以看Offer上的Partion函数，堆排序需要O(NlgN)
发表于 2016-05-14 12:45:41 回复(2)
只想有创意头像 只想有创意
快速排序改造-->部分快排， 只要排一部分就可以了， 部分区间的排序代码可以舍弃掉。
只要确保最终有50个有序就行了。

至于堆排序， 单单是构造大根堆就是nlogn了
发表于 2015-07-25 18:48:32 回复(13)
啥头像 啥
堆排序：               O(NlogK)      这里K=50，只需维持50个元素的小根堆即可
快速排序：            O(N)            借助其划分的思想

这题可能想要说明的是1000万的海量数据，这样就是堆排
发表于 2015-12-03 12:33:03 回复(0)
美团到店招聘头像 美团到店招聘
题目存疑。类快排方法和堆排序的效率究竟从哪儿开始转折，先mark
发表于 2017-03-19 20:45:59 回复(0)
木东2015头像 木东2015
快排是可以O(n)的。
发表于 2015-09-11 14:58:46 回复(1)
zhisheng_blog头像 zhisheng_blog
1：简单选择  最好时间 O(n^2)      平均时间O(n^2)      最坏时间 O(n^2)
2：直接插入  最好时间 O(n)         平均时间O(n^2)      最坏时间 O(n^2)
3：冒泡排序  最好时间 O(n)         平均时间O(n^2)      最坏时间 O(n^2)
4：希尔排序  最好时间 O(n)         平均时间O(logn)     最坏时间 O(n^s) 1<s<2
5：快速排序  最好时间 O(nlogn)  平均时间O(nlogn)   最坏时间O(n^2) 
6：堆排序      最好时间 O(nlogn)  平均时间O(nlogn)   最坏时间O(nlogn) 
7：归并排序  最好时间 O(nlogn)  平均时间O(nlogn)   最坏时间O(nlogn) 
发表于 2016-08-18 21:33:15 回复(1)
香蕉牛奶头像 香蕉牛奶
C
找出若干个数中最大/最小的前K个数，用堆排序是最好的
找最大数，用小根堆
找最小数，用大根堆
编辑于 2015-07-25 19:17:04 回复(15)
yyyylem头像 yyyylem
快排无敌~
发表于 2020-05-18 12:15:03 回复(0)
我是萌新有人信吗头像 我是萌新有人信吗
快排思想，找出第m大元素，需要O(n)，然后遍历一遍就可能以找出前m个
发表于 2019-04-05 21:39:51 回复(0)
XiaoJie头像 XiaoJie
基数排序不是可以实现线性时间复杂度的排序吗？
发表于 2018-07-11 10:15:07 回复(0)
xxxxxxxxxxxxxxxa头像 xxxxxxxxxxxxxxxa
快速选择排序的最坏时间复杂度为O(n^2)

这里是快排

这个题不知道想说明啥,1000+50log1000和1000log1000的大小关系？
稳定性再次回顾下 归并排序，基数排序，插入排序，冒泡排序是稳定的。

发表于 2018-06-13 23:32:27 回复(0)
青山崖野头像 青山崖野
堆排序：最好、最坏以及平均情况下的时间性能一样，可以理解为和初始序列无关。
              建立大顶堆，前50个非叶子结点即为最大的50个值，时间复杂度O(n)。
编辑于 2017-04-18 15:48:13 回复(0)
joyandfun头像 joyandfun
这个题目有争议
发表于 2017-03-19 18:36:54 回复(0)
Sunny_ivy头像 Sunny_ivy
不需要这50个数有序的情况当然是快排最佳啦，设置int privot = Partition(arr,low,high)；且判断privot = 50时结束递归
发表于 2016-12-17 22:44:20 回复(0)
柯排头像 柯排
建立一个50个元素的堆O（50）不是O（N）然后遍历维护的时间复杂度为O（NlogK）这是堆排序的时间复杂度
发表于 2016-05-16 15:13:52 回复(0)
uchiyou头像 uchiyou
建一个50个数的小根堆。贪心算法的思想
发表于 2016-03-21 12:44:41 回复(0)
牛客20435143头像 牛客20435143
建一个最小堆，然后树形选择排序排50次就好了， 建堆O（N）+50*log（N） 选C
我很好奇的是怎么用快排选前50个呢？又不知道50个的那个主元怎么找，谁能告诉我一下选快排的道理？
发表于 2015-09-20 10:41:22 回复(5)
_chenxi灰头像 _chenxi灰
一趟快排就可以 O（n）就可以完成
发表于 2015-08-10 22:13:44 回复(2)
提交观点

问题信息

复杂度 堆 360集团 排序
来自：360公司2014校招笔试卷
难度：
21条回答 17632浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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