基数排序

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. }