Medians and Order Statistics (次序统计)
Medians and Order Statistics
------
概述
Order Statistics:
次序统计，即 找出 n 个数中 排在 第 i 位 的那个数，记为 ith
Medians:
中位数，排在中间的数，
------
Medians 的取值
假设所有的数都不相同，则：
n = odd 时，只有1个 中间数，i = (n+1)/2,
n = even 时，有2个 中间数，i = n/2 和 i = n/2 + 1,
可以合并为：
i =
lower((n + 1)/2),
upper((n + 1)/2),
对于 odd 2者相同，对于 even 2者不同，
------
最大 & 最小 值
通过 n-1 次比较可以找出 最大 或 最小值，
如果要同时找2者，则可以合并一下，让比较次数小于 2*(n-1),因为如果一个数比另1个数小，则该数必定不是 最大值，反之亦然，
------
次序查找 - 每次分割2组 实现
概述：
通过 分隔函数实现 查找，
效率：
时间复杂度： 预期效率是 O(n)
空间复杂度： O(n)
思路：
基于 quicksort 改造，但每次只取其中的一半，从而效率降低到 O(n),
分隔函数的逻辑：
* 取分隔值，
* 如果分隔值就是目标值，则 ok
* 否则 将数组分隔为 左右2个，
* 判断目标数在哪个数组内，保留那个数组，对其循环调用分隔函数
*
时间复杂度 证明：
略，看 <算法导论> chp9.2
------
次序查找 - 每组5个分割 实现
较为复杂，最差情况下 时间复杂度为 O(n)，
参考：<算法导论> chp9.3
------
例子：
(顺序号 查找 - 每次分割2组 实现)
* js(order_statistic.js)
*
------
