liyuxia713

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 幸運草 閱讀(1115) | 評論 (0) | 編輯 收藏

隨機數的生成

posted @ 2010-01-21 15:37 幸運草 閱讀(489) | 評論 (0) | 編輯 收藏