基数排序在 Rust 中的实现 🦀

基数排序是一种非比较型的整数排序算法，它通过将整数键按照构成这些键的各个数字分组，然后对这些分组进行排序来实现排序。

• 基数排序在 Rust 中的实现 🦀
  • 1. 示例
  • 2. 代码
  • 3. 实现逻辑
    • 1. counting_sort 函数
    • 2. radix_sort 函数
    • 3. 总结
    • 4. 部分代码逻辑详解
      • 为什么要用 .rev()
        • 基数排序稳定性原理
        • 逆序遍历的作用
        • 实际例子
  • 4. 参考
  • 5. 注意

1. 示例

假设我们有一组数字，我们想通过基数排序对它们进行排序。

2. 代码

以下是 Rust 语言实现基数排序的一个简单示例：

// 计数排序辅助函数，用于基数排序中的单轮排序
fn counting_sort(arr: &mut [u32], exp: u32, radix: u32) {
    // 获取数组长度
    let n = arr.len();
    // 初始化输出数组和计数数组
    let mut output = vec![0; n];
    let mut count = vec![0; radix as usize];

    // 遍历原数组，统计每个桶的元素数量
    for &val in arr.iter() {
        // 计算当前元素在当前基数位的值（用于定位桶）
        let index = (val / exp) % radix;
        count[index as usize] += 1; // 增加对应桶的计数
    }

    // 变换计数数组，使其表示小于等于该索引的元素总数
    for i in 1..radix {
        count[i as usize] += count[(i - 1) as usize];
    }

    // 构建输出数组，确保稳定性（相同数值的原始顺序不变）
    for &val in arr.iter().rev() {
        let index = (val / exp) % radix;
        output[count[index as usize] - 1] = val; // 放入输出数组
        count[index as usize] -= 1; // 减少桶的计数，准备下一个相同桶位的元素
    }

    // 将排序后的数组复制回原数组
    arr.copy_from_slice(&output);
}

// 基数排序主函数
fn radix_sort(arr: &mut [u32], radix: u32) {
    // 基数必须大于 1
    if radix <= 1 {
        panic!("Radix must be greater than 1");
    }

    // 找出数组中的最大值，以确定需要排序的位数
    let max_val = *arr.iter().max().unwrap_or(&0u32);
    let mut exp = 1; // 初始化位权为 1（代表最低位）

    // 对每一位进行排序，直到最高位
    while max_val / exp > 0 {
        counting_sort(arr, exp, radix); // 对当前位进行排序
        exp *= radix; // 移动到下一位
    }
}

fn main() {
    // 示例数组
    let mut arr = [170, 45, 75, 90, 802, 24, 2, 66];
    let radix = 10; // 使用十进制作为基数

    println!("Original array: {:?}", arr);
    radix_sort(&mut arr, radix); // 执行基数排序
    println!("Sorted array: {:?}", arr);
}

3. 实现逻辑

实现逻辑遵循基数排序的经典步骤，主要分为两部分：counting_sort 函数和 radix_sort 函数，现在基数是作为一个参数传入的，增加了灵活性。下面是对整个实现逻辑的详细讲解：

1. counting_sort 函数

counting_sort 函数是基数排序的核心部分，它负责按照数值的一位（当前轮次的基数位）进行排序。函数接受三个参数：待排序数组的引用、当前排序的“位权”（即当前考虑的位的位置，用 exp 表示）、以及基数 radix。

• 初始化: 首先，根据原数组长度创建输出数组 output 和计数数组 count。计数数组用来统计每个桶（对应于基数的每个可能值）中的元素数量。

• 计数: 遍历原数组，根据当前位权和基数计算每个元素应该落入的桶的索引（index），并增加相应桶的计数值。这里利用了除法和取余运算（(val / exp) % radix）来定位元素的桶。

• 累计计数: 对计数数组进行变形，使每个位置 i 的值表示小于等于 i 的所有桶中元素的累计数量。这一步是为后续步骤做准备，确保元素能正确地放置在输出数组中。

• 构建输出数组: 逆序遍历原数组，这样可以保证在放入输出数组时保持稳定性（相同数值的原始顺序不变）。对于每个元素，计算其应放入的输出数组位置，然后将该元素放入 output，同时减少相应桶的计数值，确保后续相同桶位的元素能够正确放置。

• 复制回原数组: 最后，将排序好的 output 数组复制回原数组 arr，完成这一位的排序。

2. radix_sort 函数

radix_sort 函数负责调用 counting_sort 函数，按每一位（从最低位到最高位）对数组进行排序。它接收两个参数：待排序数组的引用和基数 radix。

• 基数有效性检查: 首先，检查基数是否大于 1，因为基数为 1 或更小是没有意义的，会导致无限循环或错误的结果。

• 找出最大值: 确定数组中的最大值，以便知道需要排序多少位。

• 按位排序: 通过不断调整 exp（即当前位权，初始为 1，每次乘以基数），对数组进行多次 counting_sort，每次排序都基于当前位的数值。当 max_val / exp > 0 不再成立时，说明所有位都已经排序完毕。

3. 总结

这个实现通过分步处理数组中每个数字的每一位，利用计数排序的思想，高效地完成了非比较排序。
它特别适合于整数排序，尤其是当数值范围较大但位数相对较少时效率很高。
通过将基数作为参数，该实现变得更加通用，能够适应不同基数的排序需求。

4. 部分代码逻辑详解

为什么要用 .rev()

在基数排序的 counting_sort 函数中，对原数组进行逆序遍历（.rev()）是为了确保排序的稳定性。排序稳定性意味着相等的元素在排序前后保持原有的顺序不变。

具体到这个步骤，当我们根据当前基数位构建输出数组时，逆序遍历原数组可以确保当多个元素属于同一个桶（即在同一基数位上的值相同）时，后出现的元素先被放置到输出数组中。这是因为我们在遍历过程中不断地减少桶的计数值，这样后遍历到的相同桶位元素会被放在前面遍历到的同桶元素之前，从而维持了它们原来的相对顺序。

如果不使用 .rev()，而是正向遍历，那么先遍历到的元素会后被放置到输出数组中，这将破坏原本元素的顺序，导致排序不稳定。因此，逆序遍历是确保基数排序稳定性的关键操作之一。

举例：

基数排序稳定性原理

基数排序是一种非比较排序算法，它不通过比较元素间的大小关系来决定排序顺序，而是通过分配元素到多个“桶”中，再收集这些桶来排序。为了保持排序的稳定性，即相同元素的原始顺序不变，逆序遍历在构建输出数组时起到了关键作用。

逆序遍历的作用

想象我们正在对一个数组 [345, 234, 123, 345]（每位数字代表一个位权）进行基数排序，当前轮次是按个位数排序。

1. 计算桶索引：首先，我们关注个位数，对于每个数字，计算它对应的桶索引。例如，数字 345 对应的个位是 5，所以它属于第 5 个桶。

2. 逆序遍历的重要性：现在，我们需要将这些数字分配到对应的桶中，并最终形成有序数组。如果我们正向遍历原数组，将遇到的第一个数字 345 放入桶之后，桶的计数会减一，之后再遇到同样属于第 5 个桶的数字（假设是另一个 345），它会因为计数已经减过而被放在第一个 345 后面，导致稳定性丢失。

3. 逆序遍历确保稳定性：采用逆序遍历，最后一个遇到的相同桶位的元素最先被放入输出数组，随后的相同桶位元素在计数减一后，会放在之前遇到的元素之前。这样，即使有多个相同的元素，它们在输出数组中的顺序也会保持与原数组中相同的相对顺序，即稳定性得到了维护。

实际例子

数组：[345, 234, 123, 345]

按个位排序（假设仅展示这一轮）：

1. 计算桶索引：

   • 345 -> 个位是 5
   • 234 -> 个位是 4
   • 123 -> 个位是 3
   • 345（第二个）-> 个位是 5

2. 正向遍历的问题：如果正向遍历，第一个 345 会先放入桶，之后第二个 345 放入时，由于计数已经减少，它可能会错误地放置在第一个 345 之后，破坏稳定性。

3. 逆序遍历的解决方案：逆序遍历时，第二个 345 先被处理，它被放入桶后，桶的计数减一，第一个 345 再被处理时，它会正确地排在第二个 345 之前，保持了稳定性。

通过这种方式，逆序遍历保证了基数排序在处理具有相同位值的元素时，能维持它们在原数组中的相对顺序，从而实现了排序的稳定性。

4. 参考

• Wikipedia - Radix sort
• 基数排序

5. 注意

基数排序对于数字大小有要求，它比较适合于数字位数不多的排序场景。对于数字位数很多或者数字范围很大时，可能不是最佳选择。

此外，基数排序是稳定的排序算法，它保持相等元素的原始顺序。🎈📈

在实际应用中，由于 Rust 的所有权和借用规则，实现排序算法需要特别注意变量的借用和生命周期。🧐👌