Order Statistics 顺序统计（找出第i小元素）

     摘要:
Order Statistics 顺序统计
Select(int* a, int n, int ith): 从给定的n个元素中找出第i个小的元素
思想：QuickSort的Partition方法进行分割
如果 i = rank(pivot), 则返回a[k]
如果 i < rank(pivot), 则从前半部分中找第i个小的元素
如果 i > rank(pivot), 则从后半部分中找第i-rank(pivot)个小的元素
最坏运行时间O(n^2)
平均运行时间O(nlgn)   阅读全文

幸运草 2010-01-21 16:29 发表评论