计数排序

  1. /// In place counting sort for collections of u32
  2. /// O(n + maxval) in time, where maxval is the biggest value an input can possibly take
  3. /// O(maxval) in memory
  4. /// u32 is chosen arbitrarly, a counting sort probably should'nt be used on data that requires bigger types.
  6. pub fn counting_sort(arr: &mut [u32], maxval: usize) {
  7.     let mut occurences: Vec<usize> = vec![0; maxval + 1];
  9.     for &data in arr.iter() {
  10.         occurences[data as usize] += 1;
  11.     }
  13.     let mut i = 0;
  14.     for (data, &number) in occurences.iter().enumerate() {
  15.         for _ in 0..number {
  16.             arr[i] = data as u32;
  17.             i += 1;
  18.         }
  19.     }
  20. }
  22. use std::ops::AddAssign;
  23. /// Generic implementation of a counting sort for all usigned types
  24. pub fn generic_counting_sort<T: Into<u64> + From<u8> + AddAssign + Copy>(
  25.     arr: &mut [T],
  26.     maxval: usize,
  27. ) {
  28.     let mut occurences: Vec<usize> = vec![0; maxval + 1];
  30.     for &data in arr.iter() {
  31.         occurences[data.into() as usize] += 1;
  32.     }
  34.     // Current index in output array
  35.     let mut i = 0;
  37.     // current data point, necessary to be type-safe
  38.     let mut data = T::from(0);
  40.     // This will iterate from 0 to the largest data point in `arr`
  41.     // `number` contains the occurances of the data point `data`
  42.     for &number in occurences.iter() {
  43.         for _ in 0..number {
  44.             arr[i] = data;
  45.             i += 1;
  46.         }
  48.         data += T::from(1);
  49.     }
  50. }
  52. #[cfg(test)]
  53. mod test {
  54.     use super::super::is_sorted;
  55.     use super::*;
  57.     #[test]
  58.     fn counting_sort_descending() {
  59.         let mut ve1 = vec![6, 5, 4, 3, 2, 1];
  60.         counting_sort(&mut ve1, 6);
  62.         assert!(is_sorted(&ve1));
  63.     }
  65.     #[test]
  66.     fn counting_sort_pre_sorted() {
  67.         let mut ve2 = vec![1, 2, 3, 4, 5, 6];
  68.         counting_sort(&mut ve2, 6);
  70.         assert!(is_sorted(&ve2));
  71.     }
  73.     #[test]
  74.     fn generic_counting_sort() {
  75.         let mut ve1: Vec<u8> = vec![100, 30, 60, 10, 20, 120, 1];
  76.         super::generic_counting_sort(&mut ve1, 120);
  78.         assert!(is_sorted(&ve1));
  79.     }
  81.     #[test]
  82.     fn presorted_u64_counting_sort() {
  83.         let mut ve2: Vec<u64> = vec![1, 2, 3, 4, 5, 6];
  84.         super::generic_counting_sort(&mut ve2, 6);
  86.         assert!(is_sorted(&ve2));
  87.     }
  88. }