問題描述：
在 n 個數當中找第k小元素。
輸入：
第一行輸入n的值，第二行輸入n個數，第三行輸入k的值。
輸出：
n 個數中的第k小元素。
要求：
你的算法最壞情況下應該線上性時間内完成。
示例1 ：
輸入:
5
8 1 3 6 9
3
輸出: 6
示例 2：
10
72 6 57 88 60 42 83 73 48 85
輸出: 60
對于正常解法，我們随機在數組中選擇一個數作為劃分值（pivot），然後進行快排的partation過程（将小于pivot的數放到數組左邊，大于pivot的數放到數組右邊），劃分完之後pivot的下标為i，然後判斷k與等于i的相對關系，如果k正好在等于i，那麼數組第k小的數就是pivot，如果k小于i，那麼我們遞歸對左邊再進行上述過程，如果k大于i，那我們遞歸對右邊再進行上述過程。
對于最好的情況：每次所選的pivot劃分之後正好在數組的正中間，那麼遞歸方程為T(n) = T(n/2) + n，解得T(n) = O(n)，是以此時此算法是O(n)線性複雜度的。
對于最壞情況：每次所選的pivot劃分之後都好在數組最邊上，那麼時間複雜度為O(n2)。
BFPRT算法就是在這個pivot上做文章，BFPRT算法能夠保證每次所選的pivot劃分之後在數組的中間位置，那麼時間複雜度就是O(n)。
這題規定了要線上性時間内完成第k小元素的選擇，在算法導論這本書裡面的第九章有講解過這種問題，算法的基本思想是修改快速排序算法中的主元選取方法，降低算法在最壞情況下的時間複雜度。
下述步驟來自《算法導論(第3版)》第9.3節。
在快速排序中，我們始終選擇第一個元素或者最後一個元素作為pivot，而在此算法中，每次選擇五分中位數的中位數作為pivot，這樣做的目的就是使得劃分比較合理，進而避免了最壞情況的發生。通過執行下列步驟，算法Select可以确定一個有個不同元素的輸入數組中第i小的元素：
(1) 将n個元素劃為組，每組5個，至多隻有一組由剩下的n mod 5個元素組成。
(2) 尋找這個組中每一個組的中位數，這個過程可以用插入排序，然後确定每組有序元素的中位數。
(3) 對第2步中找出的個中位數，重複步驟1和步驟2，遞歸下去，直到剩下一個數字。
(4) 最終剩下的數字即為主元pivot，用快速排序的劃分思想，把小于pivot的數全放左邊，大于它的數全放右邊。跟快速排序不同的是，這裡隻是劃分，并沒有排序。
(5) 判斷pivot的位置與k的大小，有選擇的對左邊或右邊遞歸。
快速排序的 Partition 劃分思想可以用于計算某個位置的數值等問題，可以實作 O(n)複雜度的選擇問題，之是以這種選擇算法具有線性時間，是因為沒有進行排序，并且每次都有選擇的隻對左右其中的一邊進行遞歸處理，而排序需要進行比較，并且快速排序左右兩邊都需要進行遞歸處理，即使是在平均情況下，排序也需要 O(nlogn)的時間複雜度，而這個線性時間的選擇算法沒有使用排序就解決了選擇問題。
但缺點也很明顯，最主要的就是記憶體問題，在海量資料的情況下，很有可能沒辦法一次性将資料全部加載入記憶體，這個時候這個方法就無法完成使命了。此時可以利用堆來解決，維護一個大小為 K 的小頂堆，依次将資料放入堆中，當堆的大小滿了的時候，隻需要将堆頂元素與下一個數比較：如果大于堆頂元素，則将目前的堆頂元素抛棄，并将該元素插入堆中。周遊完全部資料，Top K 的元素也自然都在堆裡面了。但是使用堆解決這個問題，時間花費為 O(nlogk)。