Rust语言实现计数排序（从零开始掌握高效非比较排序算法）

什么是计数排序？

计数排序的核心思想是：统计每个元素出现的次数，然后根据这些统计信息直接确定每个元素在输出数组中的位置。它不是基于元素之间的比较，因此不受 O(n log n) 的下限限制。

不过要注意：计数排序只适用于整数（或可以映射为整数的数据），且数据范围不能太大（否则会浪费大量内存）。它是稳定排序算法的一种，意味着相等元素的相对顺序不会改变。

Rust实现步骤详解

下面我们一步步用 Rust 实现计数排序：

1. 找出待排序数组中的最大值和最小值，确定计数数组的大小。
2. 创建一个计数数组，用于记录每个元素出现的次数。
3. 遍历原数组，统计每个元素的出现次数。
4. 根据计数数组，按顺序将元素放回结果数组。

完整Rust代码示例

下面是完整的、可运行的 Rust 计数排序实现：

fn counting_sort(arr: &Vec<i32>) -> Vec<i32> {    // 处理空数组    if arr.is_empty() {        return Vec::new();    }    // 找出最大值和最小值    let &min = arr.iter().min().unwrap();    let &max = arr.iter().max().unwrap();        // 创建计数数组，大小为 max - min + 1    let mut count = vec![0; (max - min + 1) as usize];    // 统计每个元素出现的次数    for &num in arr {        count[(num - min) as usize] += 1;    }    // 构建排序后的结果数组    let mut result = Vec::new();    for (i, &c) in count.iter().enumerate() {        for _ in 0..c {            result.push((i as i32 + min) as i32);        }    }    result}fn main() {    let data = vec![4, 2, 2, 8, 3, 3, 1];    let sorted = counting_sort(&data);    println!("原始数组: {:?}", data);    println!("排序后数组: {:?}", sorted);}

代码解析

让我们逐段分析上面的代码：

• min 和 max 的获取：使用 Rust 的迭代器方法 .min() 和 .max() 快速找到边界值。
• count 数组：大小为 max - min + 1，这样即使有负数也能正确处理（通过偏移量 min）。
• 统计阶段：将每个数字减去 min 后作为索引，增加对应计数。
• 重建阶段：遍历计数数组，按顺序将数字放回结果数组，保证了排序的稳定性。

适用场景与局限性

计数排序非常适合以下场景：

• 数据范围较小（例如 0 到 1000）
• 需要线性时间复杂度的排序
• 作为基数排序的子程序

但也有明显局限：

• 仅适用于整数或可离散化的数据
• 当数据范围很大时（如 0 到 10⁹），内存消耗过大
• 不适合浮点数排序

总结

通过本教程，你已经掌握了如何用 Rust 实现高效的计数排序算法。这种稳定排序算法虽然应用场景有限，但在合适的情况下能提供卓越的性能。希望这篇Rust排序教程对你有所帮助！

记住：理解算法原理比死记代码更重要。尝试修改上面的代码，处理负数、优化内存使用，或者将其封装成通用函数，都是很好的练习方式。

Happy Coding with Rust!