线性时间选择算法

在一个由 n 个元素组成的集合中，第 i 个顺序统计量（order statistic）是该集合中第 i 小的元素。也就是说，最小值是第 1 个顺序统计量（i = 1），最大值是第 n 个顺序统计量（i = n）。

中位数（median）是它所在集合的中点元素。当 n 为奇数时，中位数是唯一的，出现在 i = (n + 1)/2 处。当 n 为偶数时，存在两个中位数，下中位数 i = n/2 和上中位数 i = n/2 + 1 处。因此，不考虑 n 的奇偶性，中位数总是出现在 i = (n+1)/2 的中位数处。本文中所用的中位数总是指下中位数。

<a href="http://www.cnblogs.com/gaochundong/p/select_order_statistic_and_median_in_linear_time.html#select_max_min_value">选择最大值和最小值</a>

<a href="http://www.cnblogs.com/gaochundong/p/select_order_statistic_and_median_in_linear_time.html#select_median_or_any_given">选择中位数或任意位置值</a>

对于确定最大值和最小值的问题，n-1 次比较是最优的。

对于同时获取最大值和最小值，至多需要 3(n/2) 次比较就足以同时找到。如果 n 是奇数，那么总共需要 3(n/2) 次比较。如果 n 是偶数，则可先做一次初始比较，接着做 3((n - 2)/2) 次比较。

<a></a>

RANDOMIZED-SELECT 算法采用快速排序算法的思想。区别是，快速排序会递归地处理划分的两边，而 RANDOMIZED-SELECT 则只处理一边。所以快速排序的期望运行时间是 Θ(n lg n)，而 RANDOMIZED-SELECT 的期望运行时间为 Θ(n)。

RANDOMIZED-SELECT 的最坏运行时间为 Θ(n2)，即使是要选择最小元素也是如此。因为它是随机化的，该算法的平均情况性能较好。

<a>本文转自匠心十年博客园博客，原文链接：http://www.cnblogs.com/gaochundong/p/select_order_statistic_and_median_in_linear_time.html，如需转载请自行联系原作者</a>