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); } }