首页
题库
面试
求职
学习
竞赛
More+
所有博客
搜索面经/职位/试题/公司
搜索
我要招人
去企业版
登录 / 注册
首页
>
试题广场
>
设有5000个无序的元素,希望用最快的速度排出其中前50个最
[单选题]
设有5000个无序的元素,希望用最快的速度排出其中前50个最大的元素,最好选用哪种排序方法?
冒泡排序
快速排序
堆排序
基数排序
查看正确选项
添加笔记
求解答(6)
邀请回答
收藏(113)
分享
纠错
12个回答
添加回答
5
wanlanwalan
用堆排序最好,因为堆排序不需要等整个排序结束就可挑出前50个最大元素,而快速排序和基数排序都需等待整个排序结束才能知道前50个最大元素。
发表于 2017-05-06 09:27:32
回复(0)
4
大菜鸟大菜狗
答案:C
解析:
堆排序算法中,数组最大的元素位于堆顶处,在输出堆项的最大值之后,使得剩余n-1个元素的序列又建成一个堆,则得到n个元素中的次大值。如此反复执行50次,便能得到前50个最大的元素。和其他的相比堆排序只执行了50次,其他的在最坏的情况下都要遍历,所以C。
发表于 2015-09-09 00:21:25
回复(3)
3
韭菜馅饺子
C,50个数的最小堆,O(nlog50)搞定
发表于 2015-09-09 13:36:11
回复(0)
1
Jinso
堆排序之中,每一轮的排序之后,会将最大的元素排序至堆顶,然后令它与最后一个交换,来使得最大元素处于他应该处于的最右位置。依次循环多次,实现排序。要选出前多少大得到元素,则在堆排序的循环之中的合适位置跳出循环即可。
发表于 2019-04-25 20:03:14
回复(0)
1
eagle
C
构造 50个数的最小化堆, 对于接下来的新元素, 每次跟堆顶比较, 比堆顶大, 就替换堆顶, 然后调整一下,维持最小化堆的性质。
这样就可以稳定地找到50个最大的数。
快排的变体也可以完成, 不过不稳定。
发表于 2015-01-06 00:22:56
回复(0)
0
猿来
B
发表于 2018-08-09 21:00:04
回复(0)
0
Jeannie_Li
A. 冒泡:平均时间复杂度=最坏时间复杂度=O(n^2) B. 快排:平均时间复杂度=O(nlgn),最坏时间复杂度=O(n^2) C.堆排:平均时间复杂度=最坏时间复杂度=O(nlgn) D.基数:平均时间复杂度=最坏时间复杂度=O(n*k),当桶的个数和元素相同时,时间复杂度为O(n^2) 从平均时间复杂度上,首先排除A 从最坏时间复杂度上,可以排除C,D 从另一个角度分析。堆排不用等排序结束,就可以找出最大的那50个数,所以时间复杂度可以算成:50*lg5000 < 5000,而其他三个算法全部得等到排序结束以后才可以选择出最大的50个数,就算基数排序是线性的时间复杂度5000,也比50*lg5000大,所以选择堆排(C)
发表于 2018-07-01 17:35:59
回复(0)
0
麦垛上的守望者
利用快排的划分原理,不是说,可以很快地从多个数据中挑出前m个最大数吗?
怎么这里就不行了。。。
有时候是堆排序,有时候是快排,真是纠结
发表于 2018-06-05 11:00:13
回复(1)
0
lxs
选择第k元素有O(n)算法啊,就是类似快排的一次分割但是只对需一边递归选择...
但是这里你写个快排选B也不合适吧..
发表于 2015-09-11 20:41:18
回复(0)
0
鸡立鹤群
快速排序最好的时候需要O(1)次,最坏的时候需要O(N^2)次,确实不大稳定。堆排序也能完成,需要50次输出。我倒是觉得基数排序挺好,从高位到低位进行基数排序,可很快找到前50个啊!
发表于 2015-09-09 21:40:26
回复(0)
0
木子流
当然是B
发表于 2015-09-09 18:39:24
回复(0)
0
Established
开一个堆数组为50的小堆,5000个元素依次和堆顶比较,比堆顶大压进堆里,再调整堆的结构,保持为最小堆。最后得到的就是最大的50个~
发表于 2015-09-09 15:38:22
回复(0)
这道题你会答吗?花几分钟告诉大家答案吧!
提交观点
问题信息
阿里巴巴
排序
上传者:
一存光阴
难度:
12条回答
113收藏
19395浏览
热门推荐
相关试题
数据链路层滑动窗口机制中发送窗口(...
网络基础
评论
(1)
供受文者使用的具有法定效用的正式文...
京东
产品运营
2018
常识判断
行政
评论
(1)
有关linux线程的描述,正确的是...
京东
Java工程师
C++工程师
iOS工程师
安卓工程师
运维工程师
前端工程师
算法工程师
PHP工程师
2018
评论
(1)
用一种动物介绍你自己
通用能力
评论
(1)
请你说几个海量数据存储常见问题以及...
评论
(1)
扫描二维码,关注牛客网
意见反馈
下载牛客APP,随时随地刷题