奇偶排序

1. pub fn odd_even_sort<T: Ord>(arr: &mut [T]) {
2. let len = arr.len();
3. if len == 0 {
4. return;
5. }

7. let mut sorted = false;
8. while !sorted {
9. sorted = true;

11. for i in (1..len - 1).step_by(2) {
12. if arr[i] > arr[i + 1] {
13. arr.swap(i, i + 1);
14. sorted = false;
15. }
16. }

18. for i in (0..len - 1).step_by(2) {
19. if arr[i] > arr[i + 1] {
20. arr.swap(i, i + 1);
21. sorted = false;
22. }
23. }
24. }
25. }

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

31. #[test]
32. fn basic() {
33. let mut arr = vec![3, 5, 1, 2, 4, 6];
34. odd_even_sort(&mut arr);
35. assert_eq!(arr, vec![1, 2, 3, 4, 5, 6]);
36. }

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

45. #[test]
46. fn one_element() {
47. let mut arr = vec![3];
48. odd_even_sort(&mut arr);
49. assert_eq!(arr, vec![3]);
50. }

52. #[test]
53. fn pre_sorted() {
54. let mut arr = vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
55. odd_even_sort(&mut arr);
56. assert_eq!(arr, vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
57. }
58. }