查找第k小的元素(O(n)遞歸解法)

今天分享一個小技巧，雖然是小技巧但是還是很有價值的，曾經是微軟的面試題。題目是這樣的，一個無序的數組讓你找出第k小的元素，我當時看到這道題的時候也像很多人一樣都是按普通的思維，先排序在去第K個，但是當數組非常大的時候，效率不高，那有沒有簡單的方法了，其實我們早就學過，隻是我們不善于思考和變通。很多人剛開始非常熱衷于各種排序算法隻是了解卻沒深究，這個題目的複雜度是O(n)，原理就是快速排序裡面的劃分算法。

   分析：快速排序選擇一個pivot對數組進行劃分，左邊小于pivot，右邊大于等于pivot，是以我們計算左邊小于pivot(加上pivot)的個數count總共有多少，如果等于k,正是我們所要的，如果大于k，說明第k小的數在左邊，那就在左邊進行我們的遞歸；否則，在右邊，那麼說明右邊的第k-count小的數就是我們所要的，在右邊進行我們的遞歸。

代碼如下：