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