kth

数组分区及寻找第 K 个元素的算法

中位数是等于数组长度一半的顺序的元素。

crates.io

travis-ci

文档（发布版本）

文档（主分支）

Rust RFC 问题 #1470 讨论了添加类似接口。

lib.rs:

寻找第 K 个元素的算法

第 K 个元素是在数组排序后位于第 k 个索引的元素。

寻找中位数是寻找第 K 个元素的特殊情况，要寻找中位数，将 k 设置为数组长度的半数。

在寻找第 K 个元素时通常执行分区。一个数组在给定元素 X 之前的所有元素都小于 X，而在该元素 X 之后的所有元素都大于 X 时，该数组被分区。

示例

use kth::SliceExtKth;

let mut x = [6, 6, 8 ,1, 2];
// sorted =  1  2  6  6  8
let m = x.len()/2;
x.partition_by_kth(m);
println!("Median is {}", x[m]);
assert_eq!(x[x.len()/2], 6);