从一个无序数组中挑选出其中前十个最大的元素，在以下的排序方法

[单选题]

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

```
快速排序
```
```
堆排序
```
```
归并排序
```
```
基数排序
```

查看答案及解析

AlexNeverStop

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

发表于 2017-07-02 17:42:23 回复(0)

新玥

快速排序：选取一个基准数，序列最左边和最右边分别设置一个探针i,j。先从右往左找一个小于基准数的数，再从左往右找一个大于基准数的数，然后交换他们。继续从右向左重复以上过程，直至两探针相遇。最后基准数与两探针相遇位置的数进行交换。一轮排序结束后，基准数将序列分为两部分，左边的数都小于基准数，右边的数都大于基准数。平均复杂度为O(nlogn),最坏为O(n^2)。 ********************************************** 堆排序：不稳定排序，复杂度O(nlogn)。升序采用大顶堆(每个结点的值都大于或等于其左右孩子结点的值)，降序采用小顶堆。从最后一个非叶子结点开始，从左至右，从下至上调整成堆结构。一轮排序后，无序序列被构造成了一个堆，堆顶(根结点)元素为该趟排序序列最大或最小值，然后将堆顶元素与末尾元素进行交换。对剩余结点继续作上述调整。 ********************************************** 归并排序：时间复杂度O(nlogn)。将待排序序列分成两组，只需使两组分别有序，然后将两组有序数列合并完成排序。采用递归分解数列，当分出来的组只有一个数据时认为该组有序，然后依次合并相邻小组。 ********************************************** 基数排序：稳定排序。时间复杂度O(d(n＋r))。r为基数，d为位数。依次对各个位进行排序，位数不足的补齐。分为最低位优先法(LSD)和最高位优先法(MSD)。分配: 先从个位开始，根据位值分别放入0-9号桶中。收集：将桶中的数据按顺序放到数组中。同一桶中按放入顺序取出(稳定排序)。

编辑于 2018-09-19 16:37:13 回复(8)

不再是全聚德

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

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

明显是堆排序比较快啊

发表于 2017-04-15 16:05:15 回复(1)

=..=

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

发表于 2017-07-18 09:25:40 回复(7)

Yobe

https://www.cnblogs.com/onepixel/articles/7674659.html

发表于 2019-03-09 15:02:11 回复(1)

Snowly

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

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

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

编辑于 2017-02-23 16:55:56 回复(1)

HarlanZhou

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

发表于 2017-11-05 09:06:05 回复(0)

编程小白

快排，如果是非随机取划分值，对于数组接近顺序的情况要会退化为n2。随机取划分值，概率上可以提供接近On的复杂度(n+n/2+n/4+...+10)。堆排序建堆时间接近On，取最大值并调整为Olgn，所以C耗时为n+10*lgn。基数排序前提是数组元素为整型，对于double和float，甚至是非内置数据类型不适用。但是快排对于***的利用更好(顺着访问)，堆排序(跳着访问)，常数上快排小。所以考虑常数的话，快排也许好一些(其实我觉得这种题挺没意思的。。)

发表于 2017-02-25 07:45:59 回复(0)

卡布奇诺赛高

这题题意可能不是很清除,和队友讨论了一晚上大致理解了答案.

首先,快排复杂度O(nlogn)~O(n²),挺基础的不解释了

归并稳定O(nlogn)

堆排序复杂度是O(n)~O(nlogn),当阳寿插入,即插入每一个元素都不会改变堆结构,那么完全无需维护,此时就是建立一个节点为n的树,复杂度O(n),当插入的每个元素都会被旋转到根节点时复杂度O(nlogn)

基排的争议最大,一开始按O(n)算的,后来发现其实准确来说是O(nlog(n)m),log是以10为底,m是桶数,因为对纯数字排序log(n)最大19,m为10所以一般情况省略,但题目中没有保证所有元素均为数字,所以m和log(n)的复杂度是需要计入的,并且可能会出现无法使用基数排序的情况(毕竟可能需要很多的桶).

编辑于 2021-05-08 22:43:11 回复(0)