桶排序

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