Posted on 2007-09-04 18:55
ZelluX 阅读(478)
评论(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大牛 ^_^)