解答
正确答案是 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次。
大佬的文章让我受益匪浅，如痴如醉，以后的日子还希望能够得到大佬的谆谆指点
来我收藏夹吃灰吧！
简历居然还能这样写
快排的topk问题能达到On,剑指offer里面说的,这题明显不对