algorithms_fourth 0.1.10

//! 高位优先的字符串排序
//!
//!  #  使用
//! ```
//!     use algorithms_fourth::string::msd::sort;
//!         let mut src = vec!["she","sells","seashells","by","the","sea","shore","the","shells","she","sells","are","surely","seashells"];
//!         sort(&mut src);
//!         println!("{:?}",src);
//! ```
use crate::insert_sort;
/// 阀值，在阀值之下插入排序效率更高
// const M: usize = 15;
// 这里为了验证高位优先算法的正确性，所以置0
const M: usize = 0;
/// 基数
const R: usize = 256;
pub fn sort(src: &mut Vec<&str>) {
    let n = src.len();
    let mut aux = vec![""; n];
    sort_in_range(src, &mut aux, 0, n - 1, 0);
}

fn sort_in_range<'a>(src: &mut [&'a str], aux: &mut [&'a str], lo: usize, hi: usize, d: usize) {
    if hi <= lo {
        return;
    }
    if hi <= lo + M {
        // 数据量少时插入排序性价比更高
        insert_sort(src);
        return;
    }
    let mut count = [0; R + 2];
    for i in lo..=hi {
        // 计算频率。偏移2是为了在频率转化为索引后依然能存有下一位排序需要的区间信息
        // 因为char_at 默认已经偏移了1，所以这里只偏移1
        count[char_at(src[i], d) + 1] += 1;
    }
    for r in 0..R + 1 {
        // 频率转化为索引:位置r存储小于r的元素个数
        count[r + 1] += count[r];
    }

    (lo..=hi).for_each(|i| {
        // 偏移一位使得，排序结束后count前n个数据刚好是下一步所需要的区间信息
        // 因为char_at默认已经偏移了1，所以这里无需偏移
        let pos = char_at(src[i], d);
        // 注意：count中的值是从0开始的，而i是从lo开始的
        aux[count[pos]] = src[i];
        count[pos] += 1;
    });
    (lo..=hi).for_each(|i| {
        // 回写数据。aux的索引是从0开始的
        src[i] = aux[i - lo];
    });
    let d = d + 1;
    for i in 0..R {
        if count[i] < count[i + 1] {
            sort_in_range(src, aux, lo + count[i], lo + count[i + 1] - 1, d);
        }
    }
}
/// 获取对应位置字符的数字大小
/// 0:没有
/// 其他:真实位置+1
fn char_at(s: &str, d: usize) -> usize {
    s.as_bytes().get(d).map_or(0, |&f| f as usize + 1)
}
#[cfg(test)]
mod test {
    use super::sort;

    #[test]
    fn test() {
        let mut src = vec![
            "she",
            "a",
            "",
            "sells",
            "seashells",
            "by",
            "the",
            "sea",
            "shore",
            "the",
            "shells",
            "shea",
            "sells",
            "are",
            "surely",
            "seashells",
        ];
        sort(&mut src);
        println!("{:?}", src);
    }
}