11 个版本
| 0.3.0 | 2019 年 10 月 27 日 |
|---|---|
| 0.2.0 | 2019 年 10 月 27 日 |
| 0.1.8 | 2019 年 7 月 11 日 |
| 0.1.3 | 2019 年 4 月 13 日 |
#2122 在 算法 中
每月 28 次下载
6KB
71 行
Count Sort
实现计数排序算法的快速排序库，时间复杂度为 O(n + k)。适用于快速对具有较小可能值范围的大量数据进行排序。现在支持 no_std
目前仅支持 u8, u16, i8 和 i16。
目标
提高性能并减少内存使用。
性能
复制和排序以下指定长度的随机生成的 Vec 的时间。展示了哪些长度更快，以及哪些长度的开销太大。
| 长度 | sort_u8 | .sort() | .sort_unstable() | dmsort |
|---|---|---|---|---|
| 0 | 9.3944 纳秒 | 11.633 纳秒 | 11.887 纳秒 | 11.427 纳秒 |
| 1 | 24.074 纳秒 | 25.148 纳秒 | 25.700 纳秒 | 25.442 纳秒 |
| 4 | 215.06 纳秒 | 48.536 纳秒 | 49.364 纳秒 | 110.13 纳秒 |
| 16 | 370.30 纳秒 | 223.30 纳秒 | 238.12 纳秒 | 429.16 纳秒 |
| 64 | 935.84 纳秒 | 2.1638 微秒 | 1.4000 微秒 | 1.8457 微秒 |
| 256 | 2.0890 微秒 | 11.445 微秒 | 6.5242 微秒 | 7.3119 微秒 |
| 1024 | 3.8468 微秒 | 56.754 微秒 | 27.414 微秒 | 30.193 微秒 |
| 4096 | 7.3327 微秒 | 255.55 微秒 | 77.200 微秒 | 85.214 微秒 |
| 16384 | 19.219 微秒 | 1.0981 毫秒 | 233.50 微秒 | 265.55 微秒 |
| 65536 | 73.449 微秒 | 4.6771 毫秒 | 794.74 微秒 | 914.10 微秒 |
| 262144 | 296.26 微秒 | 19.938 毫秒 | 3.1294 毫秒 | 3.4867 毫秒 |
用法
在 Cargo.toml 中添加依赖项
[dependencies]
count_sort = "0.3"
使用 sort_u8、sort_u16、sort_i8、sort_i16 中的适当函数
extern crate count_sort;
fn main () {
let mut data: Vec<u8> = vec![252, 107, 81, 35, 185, 18, 175, 130, 37, 166];
count_sort::sort_u8(&mut data);
println!("{:?}", data);
}