1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103

pub fn insertsort(s: &str) -> String {
    let mut st = String::with_capacity(s.len());
    let mut si = s.chars().into_iter();
    match si.next() {
        Some(ch) => st.push(ch),
        None => return st,
    }
    while let Some(ch) = si.next() {
        let mut found = None;
        for (idx, och) in st.chars().enumerate() {
            if och >= ch {
                found = Some(idx);
                break
            }
        }
        if let Some(idx) = found {
            st.insert(idx, ch)
        } else {
            st.push(ch)
        }
    }
    st
}

pub fn bucketsort(s: &str) -> String {
    let mut buckets = [0usize; 128];
    let mut nonascii = String::new();
    for ch in s.chars() {
        if ch < (128 as char) {
            buckets[ch as u32 as usize] += 1
        } else {
            let mut found = None;
            for (idx, och) in nonascii.chars().enumerate() {
                if och >= ch {
                    found = Some(idx);
                    break
                }
            }
            if let Some(idx) = found {
                nonascii.insert(idx, ch)
            } else {
                nonascii.push(ch)
            }
        }
    }
    let mut st = String::with_capacity(s.len());
    for (chcode, &bucket) in buckets.iter().enumerate() {
        let ch = chcode as u8 as char;
        for _ in 0..bucket {
            st.push(ch)
        }
    }
    st.push_str(&nonascii);
    st
}

pub fn vecsort(s: &str) -> String {
    let mut charvec = s.chars().collect::<Vec<char>>();
    charvec.sort();
    charvec.into_iter().collect::<String>()
}

#[cfg(test)]
mod tests {
    use super::*;
    use std::time::Instant;
    use std::cmp;
    fn teststr(s: &str) {
        let strstart = Instant::now();
        let strstr = bucketsort(s);
        let strtime = strstart.elapsed();
        let insertstart = Instant::now();
        let insertstr = insertsort(s);
        let inserttime = insertstart.elapsed();
        let vecstart = Instant::now();
        let vecstr = vecsort(s);
        let vectime = vecstart.elapsed();
        assert!(strstr == vecstr);
        assert!(insertstr == vecstr);
        if s.len() != 64 {
            assert!(cmp::min(strtime, inserttime) <= vectime);
        }
    }

    #[test]
    fn test8() {
        teststr("asdfhjkl");
    }

    #[test]
    fn test64() {
        teststr("asdfhjklasdfhjklasdfhjklasdfhjklasdfhjklasdfhjklasdfhjklasdfhjkl");
    }

    #[test]
    fn test4096() { 
        let mut s = String::with_capacity(4096);
        for i in 0..4096 {
            s.push((i * 733 % 26) as u8 as char);
        }
        teststr(&s);
    }
}