设有 1000 个基本有序的元素，希望用最快的速度挑选出其中

[单选题]

设有 1000 个基本有序的元素，希望用最快的速度挑选出其中前 10 个最大的元素，最好选用（）排序法。

```
冒泡排序
```
```
快速排序
```
```
直接插入排序
```
```
归并排序
```

查看答案及解析

Miamy

我的理解应该是快速排序（改进后的）解决TOPK问题要更快一些。所以我认为这题目的答案有错，发了纠错。然后以下是系统给我的回复，我觉得很有道理，应该能帮大家解决对答案的疑惑。（顺便说一下，纠错信息居然是人工回复，这个工作听起来就很辛苦呀.....）

系统回复：

“你说的是对的，但是答案中的快排指的是整体快排，不是改进后的快排。这是这道题的原意，了解知识点就好。这是这个题的标答“A 1、因为是topN的问题，所以一般考虑“选择排序”算法，这里只有“冒泡”是选择排序。 2、虽然冒泡的时间复杂度是O(n^2),但在这里由于基本有序，且只挑选前10个元素，复杂度10n左右，而b、c、d都是要做全局的排序，没有利用“基本有序”这个特点。 3、如果没有基本有序的条件，取topN，改进的“快排”，平均效果会更好些。”

发表于 2017-07-13 17:19:10 回复(6)