一个数据表有51233个元素，如果仅要求找出其中最大的12个

[单选题]

一个数据表有51233个元素，如果仅要求找出其中最大的12个元素，采用什么算法比较节省时间 ( )。

```
堆排序
```
```
希尔排序
```
```
快速排序
```
```
直接选择排序
```

查看正确选项

neekity

TopK问题堆排序

发表于 2019-04-15 19:51:14 回复(0)

牛客382468240号

好

发表于 2022-09-06 16:51:46 回复(0)

男南楠难

思路1：利用堆排序实现
（1）取前m个元素（例如m=100），建立一个小顶堆。保持一个小顶堆得性质的步骤，运行时间为O（lgm);建立一个小顶堆运行时间为m*O（lgm）=O(m lgm);
（2）顺序读取后续元素，直到结束。每次读取一个元素，如果该元素比堆顶元素小，直接丢弃。如果大于堆顶元素，则用该元素替换堆顶元素，然后保持最小堆性质。最坏情况是每次都需要替换掉堆顶的最小元素，因此需要维护堆的代价为(N-m)*O(lgm);最后这个堆中的元素就是10亿个数据中最大的100个。时间复杂度为O(N lgm）。

发表于 2019-04-15 20:23:06 回复(1)