liyuxia713

蹒跚前行者

常用链接

统计

Algorithms

C++

最新评论

2010年1月21日 #

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)   阅读全文

posted @ 2010-01-21 16:29 幸运草 阅读(1043) | 评论 (0)编辑 收藏

随机数的生成

posted @ 2010-01-21 15:37 幸运草 阅读(422) | 评论 (0)编辑 收藏