rust-algorithms:3-桶排序
0 / 0 / 创建于 2年前
godme 的个人博客
fn bucket_sort(arr: &[usize]) -> std::vec::Vec<usize> {
if arr.is_empty() {
return vec![];
}
let len = arr.len();
let max = arr.iter().max().unwrap();
let mut buckets = vec![vec![]; len + 1];
for vp in arr.iter() {
let value = *vp;
let idx = len * value / max;
// 分桶规则一定要定好，对于每个桶一定保证
// x < y && max(x) < min(y)
buckets[idx].push(value);
}
// 桶内排序
for bucket in buckets.iter_mut() {
super::insertion_sort::insertion_sort(bucket);
}
let mut res = vec![];
// 直接收集
for bucket in buckets.iter() {
for vp in bucket {
res.push(*vp);
}
}
res
}本作品采用《CC 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号