臭皮匠排序

1. fn _stooge_sort<T: Ord>(arr: &mut [T], start: usize, end: usize) {
2. if arr[start] > arr[end] {
3. arr.swap(start, end);
4. }

6. if start + 1 >= end {
7. return;
8. }

10. let k = (end - start + 1) / 3;

12. _stooge_sort(arr, start, end - k);
13. _stooge_sort(arr, start + k, end);
14. _stooge_sort(arr, start, end - k);
15. }

17. pub fn stooge_sort<T: Ord>(arr: &mut [T]) {
18. let len = arr.len();
19. if len == 0 {
20. return;
21. }

23. _stooge_sort(arr, 0, len - 1);
24. }

26. #[cfg(test)]
27. mod test {
28. use super::*;

30. #[test]
31. fn basic() {
32. let mut vec = vec![3, 5, 6, 3, 1, 4];
33. stooge_sort(&mut vec);
34. for i in 0..vec.len() - 1 {
35. assert!(vec[i] <= vec[i + 1]);
36. }
37. }

39. #[test]
40. fn empty() {
41. let mut vec: Vec<i32> = vec![];
42. stooge_sort(&mut vec);
43. assert_eq!(vec, vec![]);
44. }

46. #[test]
47. fn reverse() {
48. let mut vec = vec![6, 5, 4, 3, 2, 1];
49. stooge_sort(&mut vec);
50. for i in 0..vec.len() - 1 {
51. assert!(vec[i] <= vec[i + 1]);
52. }
53. }

55. #[test]
56. fn already_sorted() {
57. let mut vec = vec![1, 2, 3, 4, 5, 6];
58. stooge_sort(&mut vec);
59. for i in 0..vec.len() - 1 {
60. assert!(vec[i] <= vec[i + 1]);
61. }
62. }
63. }