rust-algorithms:12-基数排序

godme 的个人博客 / 0 / 0 / 创建于 2年前


pub fn radix_sort(arr: &mut [u64]) {
    let max = match arr.iter().max() {
        Some(&v) => v as usize,
        None => return
    };
    // 基础进制
    let base = arr.len().next_power_of_two();
    // 截断数据
    let mut truncate = 1;
    while truncate <= max {
        // 计算截断后余数，也就是基础的排序（zu）
        let base_order_index = |x| x as usize / truncate % base;
        let mut orders = vec![0; base];
        // 统计排序
        for &v in arr.iter() {
            orders[base_order_index(v)] += 1;
        }
        // 传播排序，整体排序序号为len，起始为1
        for i in 1..base {
            orders[i] += orders[i - 1];
        }
        // 倒排，根据位置直接填充
        for &v in arr.to_owned().iter().rev() {
            let index = base_order_index(v);
            orders[index] -= 1;
            arr[orders[index]] = v;
        }
        // 按照下一个位置进行截断排序
        truncate *= base;
    }
}