基数排序 Radix Sort

基数排序是基于数值的每一个整数位或字符串中的每个字符来排序, 直到整个数组变得有序.

基数排序基于上文介绍的桶排序的思想.

根据排序的方向可以划分为最低位基数排序 (Least Significant Digit, LSD) 和是高位基数排序 (Most Significant Digit, MSD).

基数排序的步骤

基数排序的实现

#![allow(unused)]
fn main() {
#[allow(clippy::cast_possible_truncation)]
pub fn radix_sort(arr: &mut [u32]) {
    const fn num_digits(mut num: u32) -> usize {
        let mut count: usize = 0;
        while num != 0 {
            count += 1;
            num /= 10;
        }
        count
    }

    if arr.is_empty() {
        return;
    }
    // 获取最大的位数
    let max_digits: usize = arr
        .iter()
        .map(|num| num_digits(*num))
        .max()
        .unwrap_or_default();

    for i in 0..max_digits {
        // bucket 长度为10, 代表了数字 0~9.
        let mut buckets = vec![vec![]; 10];

        for num in arr.iter() {
            // 这个 index 是关键, 它是每个元素在当前位上的数字
            let index: u32 = *num / 10_u32.pow(i as u32) % 10;
            buckets[index as usize].push(*num);
        }

        let mut index = 0;
        for bucket in buckets {
            for num in bucket {
                // 取出对应的元素, 更新到原始数组中
                arr[index] = num;
                index += 1;
            }
        }
    }
}
}

基数排序的特点

• 基数排序是一种线性排序算法
• 时间复杂度是 O(n * m), 空间复杂度是 O(n + m), 其中 n 是数组中的个数, m 是元数的最大位数
• 可以对数值或者字符串排序
• 基数排序是稳定排序