首页 > 试题广场 >

设有5000个无序的元素,希望用最快的速度排出其中前50个最

[单选题]
设有5000个无序的元素,希望用最快的速度排出其中前50个最大的元素,最好选用哪种排序方法?
  • 冒泡排序
  • 快速排序
  • 堆排序
  • 基数排序
用堆排序最好,因为堆排序不需要等整个排序结束就可挑出前50个最大元素,而快速排序和基数排序都需等待整个排序结束才能知道前50个最大元素。
发表于 2017-05-06 09:27:32 回复(0)
答案:C
解析:
堆排序算法中,数组最大的元素位于堆顶处,在输出堆项的最大值之后,使得剩余n-1个元素的序列又建成一个堆,则得到n个元素中的次大值。如此反复执行50次,便能得到前50个最大的元素。和其他的相比堆排序只执行了50次,其他的在最坏的情况下都要遍历,所以C。
发表于 2015-09-09 00:21:25 回复(3)
C,50个数的最小堆,O(nlog50)搞定
发表于 2015-09-09 13:36:11 回复(0)
堆排序之中,每一轮的排序之后,会将最大的元素排序至堆顶,然后令它与最后一个交换,来使得最大元素处于他应该处于的最右位置。依次循环多次,实现排序。要选出前多少大得到元素,则在堆排序的循环之中的合适位置跳出循环即可。
发表于 2019-04-25 20:03:14 回复(0)
C

构造 50个数的最小化堆, 对于接下来的新元素, 每次跟堆顶比较, 比堆顶大, 就替换堆顶, 然后调整一下,维持最小化堆的性质。
这样就可以稳定地找到50个最大的数。

快排的变体也可以完成, 不过不稳定。
发表于 2015-01-06 00:22:56 回复(0)
B
发表于 2018-08-09 21:00:04 回复(0)
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)
利用快排的划分原理,不是说,可以很快地从多个数据中挑出前m个最大数吗?
怎么这里就不行了。。。
有时候是堆排序,有时候是快排,真是纠结
发表于 2018-06-05 11:00:13 回复(1)
lxs头像 lxs
选择第k元素有O(n)算法啊,就是类似快排的一次分割但是只对需一边递归选择...
但是这里你写个快排选B也不合适吧..
发表于 2015-09-11 20:41:18 回复(0)
快速排序最好的时候需要O(1)次,最坏的时候需要O(N^2)次,确实不大稳定。堆排序也能完成,需要50次输出。我倒是觉得基数排序挺好,从高位到低位进行基数排序,可很快找到前50个啊!
发表于 2015-09-09 21:40:26 回复(0)
当然是B
发表于 2015-09-09 18:39:24 回复(0)
开一个堆数组为50的小堆,5000个元素依次和堆顶比较,比堆顶大压进堆里,再调整堆的结构,保持为最小堆。最后得到的就是最大的50个~
发表于 2015-09-09 15:38:22 回复(0)