線性時間選擇算法

在一個由 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>