algorithms_fourth 0.1.10

//! 三向字符串的快速排序
//!  
//!  # 使用
//! ```
//!     use algorithms_fourth::string::quick3_string::sort;
//!         let mut src = vec![
//!             "she",
//!             "sells",
//!             "seashells",
//!             "by",
//!             "the",
//!             "sea",
//!             "shore",
//!             "the",
//!             "shells",
//!             "she",
//!             "sells",
//!             "are",
//!             "surely",
//!             "seashells",
//!         ];
//!         sort(&mut src);
//!         println!("{:?}", src);
//! ```
pub fn sort(src: &mut Vec<&str>) {
    let hi = src.len() - 1;
    sort_in_range(src, 0, hi, 0);
}

fn sort_in_range(src: &mut [&str], lo: usize, hi: usize, d: usize) {
    if hi <= lo {
        return;
    }
    // lt指向小于v的元素的位置的后一位
    let mut lt = lo;
    // gt指向大于v的元素的前一位。因为初始时没有，所以是hi
    let mut gt = hi;
    let v = char_at(src[lo], d);
    // i指向未排序的数据
    let mut i = lo + 1;
    while i <= gt {
        let t = char_at(src[i], d);
        match t.partial_cmp(&v).unwrap() {
            std::cmp::Ordering::Less => {
                exch(src, lt, i);
                // 此时i指向的数据已经排序
                lt += 1;
                i += 1;
            }
            std::cmp::Ordering::Equal => i += 1,
            std::cmp::Ordering::Greater => {
                exch(src, i, gt);
                // 此时gt指向的数据已经排序，i指向的数据没有排序
                gt -= 1;
            }
        }
    }
    if lo < lt {
        sort_in_range(src, lo, lt - 1, d);
    }
    if v > 0 {
        // 说明
        sort_in_range(src, lt, gt, d + 1);
    }
    sort_in_range(src, gt + 1, hi, d);
}

fn exch(src: &mut [&str], a: usize, b: usize) {
    src.swap(a, b)
}
/// 0: 表示不存在 <br>
/// 其他:真实位置加1<br>
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![
            "a",
            "s",
            "she",
            "sells",
            "seashells",
            "by",
            "the",
            "sea",
            "shore",
            "the",
            "shells",
            "she",
            "sells",
            "are",
            "surely",
            "seashells",
        ];
        sort(&mut src);
        println!("{:?}", src);
    }
}