要从1000个数据元素中选五个最小的，下面排序算法中，那个算

[单选题]

要从1000个数据元素中选五个最小的，下面排序算法中，那个算法最快？（）

```
希尔排序
```
```
快速排序
```
```
堆排序
```
```
简单选择排序
```

查看答案及解析

走位崴了脚

简单理解，考虑每种算法的解决问题的最坏情况，希尔排序和快速排序最坏情况O(n2)。简单选择排序1000+999+998+997+996=5000-10=4990，优于希尔和快排，堆排序是简单选择排序的优化版，优于简单选择排序。堆排序耗时可参考ChrisZZ的解析。

编辑于 2021-02-28 17:34:17 回复(0)

小公牛呦

编辑于 2017-07-17 15:33:50 回复(2)

ChrisZZ

选择答案C。

按我的理解，D选项，简单选择排序，每轮选出最小的一个元素，那么5轮就完成了任务，比较次数为1000+999+998+997+996=5000-10=4990次。

而C选项，堆排序，首先需要建堆，建堆时间复杂度是O(n)，根据《算法导论》上chap6的公式推导，建堆时间的上界是O(2n)，那么需要2000次比较。接下来依次挑选最小的元素，每次挑选完一个元素，都需要重新调整堆，调整堆的时间复杂度为O(log n)，根据《算法导论》的推导是T(n)<=T(2n/3)+O(1),把n=1024带入，发现对调整时间大约为10次，并且推导中的O(1)时间是用于调整根节点、左儿子、右儿子这3个节点的时间，显然时间开销小于10次，那么5次取最小元素的时间开销就小于5*10*10=500，所以总时间开销不足2500次。

编辑于 2017-09-08 11:06:42 回复(1)