在一个由n个元素组成的集合中，第i个顺序统计量（order statistic）是该集合中第i小的元素。本节我们将讨论如下形式的一般选择问题：
输入：一个包含n个（不同）数的集合A和数i，1<=i<=n;
输出：元素x，它恰是集合A中大于其他i-1个元素的值。
显然，我们可轻易地通过渐近最优的O(n)次比较就可以找到n个元素中的最大值和最小值。实属上，至多3[n/2](下边界)次比较就足以同时找到最大值和最小值【成对处理元素：先将一对输入元素相互比较，然后将较小者与当前最小值比较，将较大者与当前最大值比较】。
一般选择问题看起来要比找最小值的简单选择问题更难，但事实上，这两种问题的渐近运行时间却是相同的O(n)。采用一种用来解决选择问题的分治算法，即RANDOMIZED-SELECT算法。该算法以快排算法为模型，like快排将输入数组以主元素为pivot递归的进行划分，但不同于快排递归的处理两边，RANDOMIZED-SELECT只处理划分的一边，这就使得RANDOMIZED-SELECT的期望时间为O(n)【快排为O(nlogn)】。
//RANDOMIZED-SELECT PHP实现
//random-partition
function random_partition(&$array,$p,$r){
$pivot=rand($p,$r);
swap($array[$p],$array[$pivot]);
return partition($array,$p,$r);
}
function partition(&$array,$p,$r){
$key=$array[$p];
while ($p<$r) {/
while ($p<$r&&$array[$r]>$key) {$r--;}
if ($p<$r) {
$array[$p++]=$array[$r];
}
while ($p<$r&&$array[$p]<$key) {$p++;}
if ($p<$r) {
$array[$r--]=$array[$p];
}
}
$array[$p]=$key;
return $p;
}
//randomized_select
//find the ith order element
function randomized_select(&$array,$p,$r,$i){
if ($p==$r) {
return $array[$p];
}
$q=random_partition($array,$p,$r);
$k=$q-$p+1;
if ($i==$k) {
return $array[$q];
}elseif ($i<$k) {
return randomized_select($array,$p,$q-1,$i);
}else{
return randomized_select($array,$q+1,$r,$i-$k);
}
}
tips：这个程序看起来允许递归调用含有0个元素的子数组，但数学证明这种情况是不可可能发生的。RANDOMIZED-SELECT的最坏运行时间为O(n*n)【划分极不走运】。但该算法的平均性能较好，又因为它是随机化的，故没有哪一种特别的输入会导致最坏情况的发生。在平均情况下，任何顺序统计量（特别是中位数）都可以在线性时间内得到。
RANDOMIZED-SELECT的基本思想是要保证对数组的划分是个好的划分，为此我们将介绍一种新的SELECT算法，使得选择算法最坏情况下运行时间也为O(n).
该SELECT算法的递归表达式如下：
ps：本节的选择算法都是在未对数组进行排序的情况下进行的。
网友评论