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

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

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

[tag_link]

[tag_link]

【答案 1】 定义含 10 个元素的数组 A，初始时元素值均为该数组类型能表示的最大数 MAX。 for M 中的每个元素 s if (s < A[9]) 丢弃 A[9]并将 s 按升序插入到 A 中； 当数据全部扫描完毕，数组 A[0]~A[9]保存的即是最小的 10 个数。 【答案 2】 定义含 10 个元素的大根堆 H，元素值均为该堆元素类型能表示的最大数 MAX。 for M 中的每个元素 s if （s < H 的堆顶元素） 删除堆顶元素并将 s 插入到 H 中； 当数据全部扫描完毕，堆 H 中保存的即是最小的 10 个数。 组成原理 43 某 CPU 中部分数据通路如图所示，其中，GPRs 为通用寄存器组；FR 为标志寄存器，用于存放 ALU 产生的标志信息；带箭头虚线表示控制信号，如控制信号 ReaD. Write 分别表示主存读、主存写，MDRin 表示内部总线上数据写入 MDR，MDRout 表示 MDR 的内容送内部总线。 MAR