试题-希望用最快的速度从一个无序数组中挑选出其中前十个最大的元素，在以下的排序方法中（）

题目

希望用最快的速度从一个无序数组中挑选出其中前十个最大的元素，在以下的排序方法中（）

A.快速排序

B.堆排序

C.归并排序

D.基数排序

解答

正确答案是 B

用堆排序最好，因为堆排序不需要等整个排序结束就可挑出前50个最大元素，而快速排序和基数排序都需等待整个排序结束才能知道前50个最大元素。

C 6条回复评论

小小精灵

取前k大的元素，可以利用快排中间类似的思想，以一个元素为基准进行划分。堆排序建堆的时候复杂度已经是nlogn了吧，那应该和快排是一个数量级了吧。

发表于 2018-10-13 11:23:37

碎梦不是梦碎

1. O(n^2)

2. O(n+10logn)

3. O(nlogn)

4. O(n)

当然本题不考虑建堆时间所以2为O(logn)

发表于 2018-10-13 11:23:26

花花

堆排序就是变向的二叉树吧，所以堆排序快！

发表于 2018-10-13 11:22:50

人间喜剧

堆排序建堆需要o(n)，每次取最大需要o(lgn),所以只要o(n+10lgn)

基数排序需要全部排好才能取出10个最大的，o（d(n+k)）

明显是堆排序比较快啊

发表于 2018-10-13 11:22:40

米米大户

选快排吧快排有一种不需要全部排序的算法，只需要得到倒数第十个位置就可以了啊

发表于 2018-10-13 11:22:30

虹猫

D，题目不在乎空间只要速度，没记错应该是基数排序最快且稳定。

如果结合实际（顾及空间开销）考虑的话，我会选择堆排序，因为ABC时间复杂度（O（N*logN））虽然一样，但是堆排序在建堆（时间复杂度近似O（N））之后取十次大根堆的堆顶就行了，即不需要执行完整个堆排序，但A和C需要走完排序流程后才能取到最大十个元素。

PS：总结起来就是，这个题目我选D，仅在只看时间开销时，但实际情况多用堆排序。

发表于 2018-10-13 11:22:15