桶排序

  1. /// Sort a slice using bucket sort algorithm.
  2. ///
  3. /// Time complexity is `O(n + k)` on average, where `n` is the number of elements,
  4. /// `k` is the number of buckets used in process.
  5. ///
  6. /// Space complexity is `O(n + k)`, as it sorts not in-place.
  7. pub fn bucket_sort(arr: &[usize]) -> Vec<usize> {
  8.     if arr.is_empty() {
  9.         return vec![];
  10.     }
  12.     let max = *arr.iter().max().unwrap();
  13.     let len = arr.len();
  14.     let mut buckets = vec![vec![]; len + 1];
  16.     for x in arr {
  17.         buckets[len * *x / max].push(*x);
  18.     }
  20.     for bucket in buckets.iter_mut() {
  21.         super::insertion_sort(bucket);
  22.     }
  24.     let mut result = vec![];
  25.     for bucket in buckets {
  26.         for x in bucket {
  27.             result.push(x);
  28.         }
  29.     }
  31.     result
  32. }
  34. #[cfg(test)]
  35. mod tests {
  36.     use super::super::is_sorted;
  37.     use super::*;
  39.     #[test]
  40.     fn empty() {
  41.         let arr: [usize; 0] = [];
  42.         let res = bucket_sort(&arr);
  43.         assert!(is_sorted(&res));
  44.     }
  46.     #[test]
  47.     fn one_element() {
  48.         let arr: [usize; 1] = [4];
  49.         let res = bucket_sort(&arr);
  50.         assert!(is_sorted(&res));
  51.     }
  53.     #[test]
  54.     fn already_sorted() {
  55.         let arr: [usize; 3] = [10, 9, 105];
  56.         let res = bucket_sort(&arr);
  57.         assert!(is_sorted(&res));
  58.     }
  60.     #[test]
  61.     fn basic() {
  62.         let arr: [usize; 4] = [35, 53, 1, 0];
  63.         let res = bucket_sort(&arr);
  64.         assert!(is_sorted(&res));
  65.     }
  67.     #[test]
  68.     fn odd_number_of_elements() {
  69.         let arr: Vec<usize> = vec![1, 21, 5, 11, 58];
  70.         let res = bucket_sort(&arr);
  71.         assert!(is_sorted(&res));
  72.     }
  74.     #[test]
  75.     fn repeated_elements() {
  76.         let arr: Vec<usize> = vec![542, 542, 542, 542];
  77.         let res = bucket_sort(&arr);
  78.         assert!(is_sorted(&res));
  79.     }
  80. }