中位数之第K小的线性选择算法

1973年，Blum、Floyd等几位大仙合并一体，写了一篇题为 “Time bounds for selection” 的章，给出了一种在数组中选出第k小元素的算法，俗称"中位数之中位数算法"。该算法从理论上保证了最坏情形下的线性时间复杂度（O(n)）。而一个简单的排序算法像快速排序的时间复杂度是O(nlogn)，利用类似于快速排序的做法是：首先对该无序数组进行排序（O(nlogn)），然后进行一次遍历（O(k)）就可以找到第k小元素。下面我们来重点看看中位数排序法。

该算法使用分而治之的策略，查找到第K小元素在最坏情况下的时间复杂度为O(n)。

实现该算法的步骤如下：

1.如果n是一个比较小的数，比如n<6，那么只需要对此无序数组进行排序后，即可很容易的得到第K小元素。

此时约束时间T=7。

2.如果n>5，那么我们将这个无序数组分成五组。此时约束时间T=n/5。

3.找出每组的中位数，构成集合M。此时的约束时间T=7n/5.

4.递归的调用selection(M,|M|/2)算法查找上一步中所有中位数的中位数，设为m。此时的约束时间

T=T（n/5）。

5.用m来分割此时的数组，比较m与其他的（n-1）个数，小于m的数置于左集合L，大于m的数置于右集合R。当

然，中位数m的下标r=|L|+1(|L|是左集合L的个数)。此时的约束时间T=T（n）。

如果r=k,那么返回m。

如果r<k,那么在小于m的左集合L中递归查找第K小数。

如果r>k,那么在大于m的右集合R中递归查找第K小数。

递归方程：T(n)=O(n) + T(n/5) + T(7n/10) （证明过程略）

如果你想知道怎样得到次方程的，不妨找一本关于算法的书看一看或直接给我留言，谢谢！

另外，我想说的是：我为什么分为五组而不是分为其他的组。

假设我们将此数组分为三组，那么有：T(n) = O(n) + T(n/3) + T(2n/3) so T(n) > O(n)。如果我

们将此数组分成五组以上，那么就会显得有些麻烦了，所以分为五个组是最理性的选择。

由于鄙人的翻译水平所致，文中不妥之处还望各位指出来，谢谢！

评论

1 楼 wjmcmcmc 2016-09-06  

r>k 左集合；
r<k 右集合。