Tag: quick selection

這個問題是小時候在一些程式競賽的書上看到的。雖然感覺很酷炫，但因為教科書上沒有教，考試也不會考，感覺會了這個也不太實用，應該只有打程式競賽時會用到，就先一直記在心底沒有拿出來想。這次看了篇文章介紹這個演算法，算是把他研究清楚一些了。有找到一個 O(n) 為線性的演算法可以用來計算中位數。其實也不只是可以計算中位數，可以改為計算第 k 位數，或是任何的百分位數。