梦里飞雪飘

问题一：最大值、最小值问题

输入：数组A[i,…,j]

输出：max和min

法一：遍历两次分别找到max和min，共需2n-2次

法二：归并思路，同时找到max和min，共需3/2n-2次

​

拓展--线性时间的选择问题（中位数和顺序统计量）

法一：按照快速排序的思路递归查找主元，最坏情况O（n^2）

法二：线性时间内的选择算法--分治法

过程：

1. 分组：每组5个数，最后一组可能不足5个
2. 排序：选择每组的中位数
3. 选择：中位数中的中位数（MoM）

​

1. 划分：用MoM中心作为划分，记它的坐标为k
2. 递归运算：

​

时间复杂度分析：

伪代码