（10 分）现有 n(n>100000)个数保存在一维

（10 分）现有 n(n>100000)个数保存在一维数组 M 中，需要在查找 M 中最小的 10 个数。 请回答下列问题。 

（1）设计一个完成上述查找任务的算法，要求平均情况下的比较次数尽可能少，简述其算法 思想（不要程序实现）。

（2）说明你所设计的算法平均情况下的时间复杂度和空间复杂度。

【答案解析】

（1）算法思想

【答案一】

定义含 10 个元素的数组 A，元素值均为该数组类型能表示的最大数 MAX。

for M 中的每个元素 s

if（s

当数据全部扫描完毕，数组 A 中保存的就是最小的 10 个数。

【答案二】

定义含 10 个元素的大根堆 H，元素值均为该堆元素类型能表示的最大数 MAX。

for M 中的每个元素 s

if（s

当数据全部扫描完毕，堆 H 中保存的就是最小的 10 个数。

（2）算法平均情况下的时间复杂度是 O（n），空间复杂度是 O(1)