【正确答案】 D

【答案解析】解析：本题相当于从n个元素选取k(k＜＜n)个元素用什么排序方法最好。起泡排序和简单选择排序第1趟比较n一1次选出最小／最大元素，第2趟比较n一2次，选出次小／次大元素，因此，这两种排序方法不予考虑。若选最小，快速排序和起泡排序差不多。希尔排序只有等排序结束才能有最后结果，这里不予考虑。堆排序建堆选出最小／最大元素，比较了至多不超过4n次，以后每选出一个元素需要logn次的比较。由此，本题的答案应该选D。但是编者还有另外的分析。若先用快速排序选出第k个最小元素，则比较次数在O(n)级，算法见下面“五、27”。对前面k-1个记录可以采用任何简单(不使用适合大数据量的堆排序等)排序方法，即使再用快速排序，也是可以的。这里n大到什么程度，k小到什么程度，会有个阈值。