Posted on 2007-09-04 18:55
ZelluX 閱讀(488)
評論(0) 編輯 收藏 所屬分類:
Algorithm
一種做法是用最差情況下復雜度也是O(n)的算法求出第k大的數，然后把這個數作為pivot進行一次paritition，再排序該數左邊的部分。復雜度為O(n + klgk)
http://en.wikipedia.org/wiki/Selection_algorithm
另外，CLRS上Selection in worst-case linear time算法實際上對in expected linear time在選數時做了一個優化，這樣在最差情況下也有O(n)的復雜度了，實際應用中沒什么用 (thx to Peter大牛 ^_^)