地精排序

1. use std::cmp;

3. pub fn gnome_sort<T>(arr: &[T]) -> Vec<T>
4. where
5. T: cmp::PartialEq + cmp::PartialOrd + Clone,
6. {
7. let mut arr = arr.to_vec();
8. let mut i: usize = 1;
9. let mut j: usize = 2;

11. while i < arr.len() {
12. if arr[i - 1] < arr[i] {
13. i = j;
14. j = i + 1;
15. } else {
16. arr.swap(i - 1, i);
17. i -= 1;
18. if i == 0 {
19. i = j;
20. j += 1;
21. }
22. }
23. }
24. arr
25. }

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

31. #[test]
32. fn basic() {
33. let res = gnome_sort(&vec![6, 5, -8, 3, 2, 3]);
34. assert_eq!(res, vec![-8, 2, 3, 3, 5, 6]);
35. }

37. #[test]
38. fn already_sorted() {
39. let res = gnome_sort(&vec!["a", "b", "c"]);
40. assert_eq!(res, vec!["a", "b", "c"]);
41. }

43. #[test]
44. fn odd_number_of_elements() {
45. let res = gnome_sort(&vec!["d", "a", "c", "e", "b"]);
46. assert_eq!(res, vec!["a", "b", "c", "d", "e"]);
47. }

49. #[test]
50. fn one_element() {
51. let res = gnome_sort(&vec![3]);
52. assert_eq!(res, vec![3]);
53. }

55. #[test]
56. fn empty() {
57. let res = gnome_sort(&Vec::<u8>::new());
58. assert_eq!(res, vec![]);
59. }
60. }