floydrivest

一个轻量级的crate，将nth_element引入Rust。可在crates.io上找到。

安装

确保你的Cargo.toml看起来像这样

[dependencies]
floydrivest = "0.2.4"

使用

将crate引入作用域

extern crate floydrivest;

use floydrivest::nth_element;

然后只需在vector上调用nth_element。

let mut v = vec![10, 7, 9, 7, 2, 8, 8, 1, 9, 4];
nth_element(&mut v, 3, &mut Ord::cmp);

assert_eq!(v[3], 7);

此实现还可以处理满足PartialEq和PartialOrd特征的泛型数据类型。

实现

链接到包含ALGOL60伪代码的原始论文。

性能

弗洛伊德和里维斯的查找第k小元素算法在平均情况下最多需要 n + min(k, n−k) + o(n) 次比较，并且有很高的概率。以下是另一篇论文的链接。

基准测试

以下是与其他crate的基准测试： order-stat，kth 和 pdqlselect。感谢 ilyapopov。