基数排序

  1. /// Sorts the elements of `arr` in-place using radix sort.
  2. ///
  3. /// Time complexity is `O((n + b) * logb(k))`, where `n` is the number of elements,
  4. /// `b` is the base (the radix), and `k` is the largest element.
  5. /// When `n` and `b` are roughly the same maginitude, this algorithm runs in linear time.
  6. ///
  7. /// Space complexity is `O(n + b)`.
  8. pub fn radix_sort(arr: &mut [u64]) {
  9.     let max: usize = match arr.iter().max() {
  10.         Some(&x) => x as usize,
  11.         None => return,
  12.     };
  13.     // Make radix a power of 2 close to arr.len() for optimal runtime
  14.     let radix = arr.len().next_power_of_two();
  15.     // Counting sort by each digit from least to most significant
  16.     let mut place = 1;
  17.     while place <= max {
  18.         let digit_of = |x| x as usize / place % radix;
  19.         // Count digit occurrences
  20.         let mut counter = vec![0; radix];
  21.         for &x in arr.iter() {
  22.             counter[digit_of(x)] += 1;
  23.         }
  24.         // Compute last index of each digit
  25.         for i in 1..radix {
  26.             counter[i] += counter[i - 1];
  27.         }
  28.         // Write elements to their new indices
  29.         for &x in arr.to_owned().iter().rev() {
  30.             counter[digit_of(x)] -= 1;
  31.             arr[counter[digit_of(x)]] = x;
  32.         }
  33.         place *= radix;
  34.     }
  35. }
  37. #[cfg(test)]
  38. mod tests {
  39.     use super::super::is_sorted;
  40.     use super::radix_sort;
  42.     #[test]
  43.     fn empty() {
  44.         let mut a: [u64; 0] = [];
  45.         radix_sort(&mut a);
  46.         assert!(is_sorted(&a));
  47.     }
  49.     #[test]
  50.     fn descending() {
  51.         let mut v = vec![201, 127, 64, 37, 24, 4, 1];
  52.         radix_sort(&mut v);
  53.         assert!(is_sorted(&v));
  54.     }
  56.     #[test]
  57.     fn ascending() {
  58.         let mut v = vec![1, 4, 24, 37, 64, 127, 201];
  59.         radix_sort(&mut v);
  60.         assert!(is_sorted(&v));
  61.     }
  62. }