在之前Python系列當中，我們介紹了heapq這個庫的用法，它可以在O(nlogn)的時間裡篩選出前K大或者前K小的元素。今天我們一起來看一個可以更快實現選擇的快速選擇算法。
思維推導
在公佈答案之前，我想先帶著大家試著推導一下解法。這其實才是算法能力的精髓，即是應用已知能力解決未知問題的能力。我們學的各種各樣的算法都可以看成是已知能力，已知能力越多，說明能力的邊界越廣，也就意味著理論上可以解決的問題也就越多。相比已知能力，解決問題的能力同樣重要，尤其是當我們有了一定的基礎之後，這一點甚至更加重要。因為有了這項能力，在一些極端情況下我們甚至可以自己推導出新算法，也即是開創和創新。
假設當下我們並不知道正確的解法是什麼，我們想要儘可能快地找到前K大的元素。如果一個一個找這個過程會很慢，除非我們可以做到常數級的查找。顯然這是不可能的，因為即使是平衡樹這類快速查找的數據結構，單次查找也需要。所以一個一個找是不行的。那麼就只剩下一批一批找，批量查找又有兩種，一種是直接查找K個，還有一種是多次查找，最後得到正解。
我們並不知道哪種方法更靠譜，但是第一種看起來不太可行，因為它就是問題本身，第二種方法看起來稍微可行一些。在這個問題下，我們並沒有多餘的信息，想要直接查找K個元素應該不太容易。所以可能通過多次查找得到解是比較好的方法。多次查找也可以簡單分為兩種情況，一種是每次查找一批，最後合併在一起，還有一種是每次縮小查找的範圍，最後鎖定答案。
到這裡，如果你對分治算法熟悉的話，你會覺得它和分治算法的應用場景很相似。我們想要求解一個比較大的問題，但是直接求解很困難，所以我們將它拆解，將大問題拆解成小問題，通過對小問題的解決來搞定原本的大問題。
我們目前比較熟悉的分治算法好像只有歸併排序和快速排序這兩個，我們可以試著把這兩個算法往這個問題上套。歸併排序核心思路是每次將數組一分為二，然後通過這兩個數組歸併的過程找到我們想要的解法。這個方案可行，但是和排序並沒有區別。我們文章開頭就已經說過了，我們想要尋找的是比排序更快的算法。再看快排，它每次是設置一個標杆，然後對數組當中的元素進行調整，保證比標杆小的元素都在它的左邊，比它大的都在它的右邊。標杆最後在的位置就是數據有序之後它正確的位置。這個方法好像和我們想要的很接近。
於是，我們就這樣順藤摸瓜，找到了正確的方法。當然實際的思考過程可能要比這個複雜，考慮的情況也會更多，但是總體的思維推導過程應該是差不多的。同樣是解題，新手往往靠靈光一閃，而高手都是有一個完整的思維鏈。很多算法問題看起來一頭霧水，但其實是有跡可循的。訓練出一個思維模型來尋找正確的解法是新手通往高手的必經之路，也是算法能力的核心。
算法原理
我們來仔細分析一下，一次快速排序的調整之後，我們可以確定標杆的位置，這樣一來就有三種情況。第一種，它所在的位置剛好是K，說明它前面的這一段數組就是答案，直接返回即可。如果它小於K，說明這個標杆取小了，我們應該在它右側的數組當中重新選擇一個標杆。如果它大於K說明這個標杆取大了，我們可以直接忽略它右側的元素，因為它右側的元素一定不在答案裡。
我們可以參考一下下面這張圖：
思路有了，代碼就不難寫了：
複雜度分析
寫完了代碼，我們來分析一下算法的複雜度。有些同學可能會有些疑惑，這個算法和快排基本上一樣，為什麼會更快呢？
這是因為我們每次迭代的過程中，數組都會被捨棄一部分，我們把完整的搜索樹畫出來大概是下面這個樣子。
可以看到，雖然總的迭代次數還是 log2n 次，但是每一層當中遍歷的元素個數不再是n。我們假設每次迭代數組的長度都會折損一半，到數組長度等於1的時候結束。我們把每一層遍歷的長度全部相加，就得到了一個等比數列：
這個等比數列的長度是log2n，我們套用等比數列求和公式：
也就是說雖然它的形式看起來和快排很接近，但是由於我們在遍歷的過程當中，每次都會縮小遍歷的範圍，所以整體的複雜度控制在了 O(n) 。當然這也只是理想情況下的複雜度，一般情況下隨著數據分佈的不同，實際的複雜度也會稍有浮動。可以理解成乘上了一個浮動的常數。
之前我們分析快排的時候曾經得出過結論，如果原始數組是逆序的，那麼快排的複雜度會退化到O(n^2)。我們當前的快速選擇算法和快排算法幾乎如出一轍，整個的思路是一樣的，也就是說，在數組是逆序的情況下同樣會遇到複雜度降級的問題。不過好在這個問題並不是不可解的，我們下面就來分析一下關於這種情況的優化。
優化探索
優化目標很明顯，就是極端情況下複雜度會出現降級的情況。問題出現的原因也已經知道了，是由於數組逆序，並且我們默認選擇最後一個元素作為標杆。所以想要解決這個問題的入手點就有兩個，一個是數組逆序的情況，一個是標杆的選擇。
相比於標杆的選擇來說，數組逆序情況的判斷不太可取。因為對於不是嚴格逆序的數組，也一樣可能出現複雜度很大的情況。如果我們通過逆序數來判斷數組的逆序程度，又會帶來額外的開銷，所以只能從標杆的選擇入手。之前我們默認選擇最後一個元素，其實這並不是元素位置的問題，無論選擇什麼樣的位置，都有可能出現對應的極端情況使得複雜度升級，所以簡單地改變選擇的位置是不能解決問題的，我們需要針對這個問題單獨設計算法。
一個比較簡單的思路是我們可以選擇首尾和中間三個位置的元素，然後選擇其中第二大的元素作為標杆。這種方案實現簡單，效果也不錯，但是分析一下的話，其實沒有從根本上解決問題，因為依然還是可能出現極端情況，比如首尾和中間剛好是三個最大的元素。雖然這個概率比單個元素出現最大降低了很多。還有一個問題是，這樣選出來的標杆不能保證分割出來的數組是平衡的。
BFPRT算法
這裡要給大家介紹一個牛哄哄的算法，說它牛不是因為它很難，而是因為它真的很牛。它的名字叫BFPRT，是由Blum、Floyd、Pratt、Rivest、Tarjan五位大牛一起發明的。如果你讀過《算法導論》的話，一定會找到其中好幾個人的名字。該算法可以找到一個比較合適的標杆，用來在快排和快速選擇的時候切分數組。
算法的流程很簡單，一共只有幾個步驟：
- 判斷數組元素是否大於5，如果小於5，對它進行排序，並返回數組的中位數
- 如果元素大於5個，對數組進行分組，每5個元素分成一組，允許最後一個分組元素不足5個。
- 對於每個分組，對它進行插入排序
- 選擇出每個分組排序之後的中位數，組成新的數組
- 重複以上操作
算法思路很樸素，其實就是一個不斷選擇中位數的過程。我們先來證明它的正確性，我們假設最終選出來的數是x，一個長度為n的數組會產生n/5個分組。由於我們取的是中位數的中位數，所以在這n/5個分組當中，有一半的中位數小於x，還有一半大於x。在中位數大於它的分組當中至少有3個元素大於等於它，所以整體而言，至少有 n/10 * 3 = 0.3n的元素大於等於x，同理也可以證明有30%元素小於等於x。所以最壞的情況選出來的x是70%位置的數。
最後，我們來分析一下它的複雜度，我們可以得到一個不等式：
其中T(n/5)是尋找 n/5 箇中位數的複雜度，T(7n/10) 是遞歸的最壞的情況，即只能減少30%數組的長度。cn 是我們使用插入排序進行多次排序的複雜度，這裡的c是一個常數。
我們很容易可以證明 T(n) = T(n/2) + cn和 T(n) = T(7n/10)+cn都是 O(n) 的複雜度，這裡我們證明一下前者作為一個例子：
我們把這個式子累加起來，可以得到：
同理，我們也可以證明 T(n) = T(7n/10)+cn 也是 O(n) 的算法，所以
也是O(n) 的算法。
根據BFPRT算法的定義很容易寫出代碼，既可以用迭代實現，也可以使用遞歸，這裡我們採用遞歸的形式：
這個代碼寫出來了之後，剩下的就容易了，改動量並不大，只需要加上兩行即可。：
看代碼的話和上面基本上沒有什麼差別，唯一的不同就是選擇之前先獲取了一下標杆。在這裡我只是在一開始的時候調用了一次，當然也可以在while循環裡每一次都調用，不過我個人覺得沒什麼必要，因為在獲取標杆的時候，會將數組全部打亂，足夠避免極端情況了。
今天的文章篇幅有點長，但內容還可以，尤其是BFPRT算法，真的是非常經典，算得上是不復雜但是很巧妙了。感興趣的同學可以瞭解一下它背後五個大佬的故事，估計比我的文章精彩得多。
好了，今天的文章就是這些，如果覺得有所收穫，請順手點個關注或者轉發吧，你們的舉手之勞對我來說很重要。
閱讀更多 承志的算法課堂 的文章
