求基於比較的最快中位數演算法（最壞情況是O(n)）？
12-30
C++ 的 std::nth_element 的平均複雜度是 O(n) ，如果用Introselect演算法實現的話，最壞複雜度也是O(n)。
演算法導論裡面的順序統計學的那一章有講一個最壞複雜度為線性的選擇演算法，並給出了複雜度分析，自己去看吧，代碼自己寫。自己搜索BFPRT。
只求中位數，要求O(n)，參考 median of medians. 此演算法可用在quicksort 和 quickselect 中，以O(n) 的時間找到pivot點進行partition，可以將quicksort的最壞時間複雜度降低至O(nlgn) ，quickselect降至 O(n)。但實際上median of medians 的O(n)常數很大，真實情況下並沒有 基於random pivot的quickselect 好。
快速選擇演算法
推薦閱讀：