std::nth_element保證在O(n)的時間複雜度內求出陣列中第k大的數字
http://www.cplusplus.com/reference/algorithm/nth_element/
用法網路上應該有很多說明，在此就不再解說了，不過關於它的原理網路上的中文文章就有點少了
nth_element使用的演算法是Introselect，Introselect算是優化過後的Quickselect
Quickselect的概念大概是做一半的Quicksort，Quicksort平均來說需要做lg(n)次，每次O(n)，但Quickselect每次只需做和自己相關的那一半就好了，也就是說第1次O(n),第2次O(n/2),第3次O(n/4),第4次O(n/8)…，n+n/2+n/4+n/8+n/16…=2*n，因此總複雜度為O(n)
但Quickselect有個問題就是在worse case下，會造成總共做了n次，總複雜度因次退化為O(n2)，因此Introselect在發現可能會發生worse case的情況下，會自動改用別的演算法(例如:median-of-medians)，這部分怎麼轉換我就沒仔細研究了(參考資料5)。我想這作法就大概像std::sort的Introsort類似，遇到worse case時就換成常數較大的heapsort。
研究了老半天，不過競賽上基本上就只要會用std::nth_element就好啦! 反正我就算研究完了還是不會想要自己寫一個Introselect或Median of medians
送大家一個nth_element範例: http://ideone.com/o1Aoh6
參考資料:
- https://en.wikipedia.org/wiki/Selection_algorithm 找出第k大數的演算法應該就叫做Selection algorithm
- https://en.wikipedia.org/wiki/Introselect
- https://en.wikipedia.org/wiki/Quickselect
- http://stackoverflow.com/questions/29145520/how-is-nth-element-implemented
- http://stackoverflow.com/questions/7358912/worst-case-on-algorithm-for-doing-k-selection 有不錯的說明
- http://blog.csdn.net/xuqingict/article/details/25488865 簡體中文文章，不過感覺有一點怪怪的
- http://www.csie.ntnu.edu.tw/~u91029/SequenceManipulation.html#3 演算法筆記其實也有相關的教學