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 | |
} |
rust-algorithms:3-桶排序
Rust
340
0
0
2022-11-10