Randomize select algorithm 随机选择算法

从一个序列里面选择第k大的数在没有学习算法导论之前我想最通用的想法是给这个数组排序，然后按照排序结果返回第k大的数值。如果使用排序方法来做的话时间复杂度肯定至少为o（nlgn）。

问题是从序列中选择第k大的数完全没有必要来排序，可以采用分治法的思想解决这个问题。randomize select

算法的期望时间复杂度可以达到o（n），这正是这个算法的迷人之处。具体的算法分析可以在《算法导论》这本书里查看。

贴出伪代码：

这个算法的思想其实跟quik-sort有些相似，采用分治法的思想来解决。首先选择一个主元pirvot：

q，将序列中的元素分为两个集合q，w，q里面的元素都小于主元pirvot，w里面的元素都大于pirvot。然后递归的调用这个过程可以得到我们想要的第i大的元素。这里的划分有三种情况：

1：主元的选择正好是第i大的元素，那么返回这个元素即可

2：q里面的元素个数 k=(q-p+1) 大于i，代表第i大的元素还在q这个集合里，那么继续这个过程寻找第i小的元素（ step 7-8）

3：q里面的元素个数 k=(q-p+1)

小于i，代表已经找到了k个小的元素，那么第i小的元素一定在w这个集合里，只要在w集合里寻找第（i-k）小的元素即可

下面给出这个算法的java实现：