algorithms_fourth 0.1.10

//! 低位优先的字符串排序
//! #使用
//! ```
//!    use algorithms_fourth::string::lsd::sort;
//!         let mut src = vec!["4pgc938","2iye230","3ci0720","1ick750","1ohv845","4jzy524","1ick750","3ci0720","1ohv845","1ohv845","2rla629","2rla629","3atw723"];
//!         sort(&mut src,7);
//!         for item in src.iter() {
//!             println!("{}",item);
//!         }
//! ```
const R: usize = 256;

pub fn sort(src: &mut Vec<&str>, w: usize) {
    let n = src.len();
    let mut aux = vec![""; n];
    for d in (0..w).rev() {
        let mut count = [0usize; R + 1];
        (0..n).for_each(|i| {
            //   获取目标字符串第d个字符在编码中的位置
            let pos = { src[i].as_bytes()[d] as usize };
            // 对应位置的计数加1,位置索引从0开始。目的是将频率转化为索引，所以0索引的值一定是0，所以需要偏移
            count[pos + 1] += 1;
        });
        for r in 0..R {
            //  当前位置的计数 加上 后一个位置的计数 等于 后后一个位置的总计数
            count[r + 1] += count[r];
        }
        (0..n).for_each(|i| {
            let pos = src[i].as_bytes()[d] as usize;
            aux[count[pos]] = src[i];
            count[pos] += 1;
        });
        (0..n).for_each(|i| {
            src[i] = aux[i];
        });
    }
}
#[cfg(test)]
mod test {
    use super::sort;

    #[test]
    fn test() {
        let mut src = vec![
            "4pgc938", "2iye230", "3ci0720", "1ick750", "1ohv845", "4jzy524", "1ick750", "3ci0720",
            "1ohv845", "1ohv845", "2rla629", "2rla629", "3atw723",
        ];
        sort(&mut src, 7);
        for item in src.iter() {
            println!("{}", item);
        }
    }
}