rust-algorithms:12-基数排序


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;
    }
}
本作品采用《CC 协议》,转载必须注明作者和本文链接
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!