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實作：