鸡尾酒排序

1. pub fn cocktail_shaker_sort<T: Ord>(arr: &mut [T]) {
2. let len = arr.len();

4. if len == 0 {
5. return;
6. }

8. loop {
9. let mut swapped = false;

11. for i in 0..(len - 1).clamp(0, len) {
12. if arr[i] > arr[i + 1] {
13. arr.swap(i, i + 1);
14. swapped = true;
15. }
16. }

18. if !swapped {
19. break;
20. }

22. swapped = false;

24. for i in (0..(len - 1).clamp(0, len)).rev() {
25. if arr[i] > arr[i + 1] {
26. arr.swap(i, i + 1);
27. swapped = true;
28. }
29. }

31. if !swapped {
32. break;
33. }
34. }
35. }

37. #[cfg(test)]
38. mod tests {
39. use super::*;

41. #[test]
42. fn basic() {
43. let mut arr = vec![5, 2, 1, 3, 4, 6];
44. cocktail_shaker_sort(&mut arr);
45. assert_eq!(arr, vec![1, 2, 3, 4, 5, 6]);
46. }

48. #[test]
49. fn empty() {
50. let mut arr = Vec::<i32>::new();
51. cocktail_shaker_sort(&mut arr);
52. assert_eq!(arr, vec![]);
53. }

55. #[test]
56. fn one_element() {
57. let mut arr = vec![1];
58. cocktail_shaker_sort(&mut arr);
59. assert_eq!(arr, vec![1]);
60. }

62. #[test]
63. fn pre_sorted() {
64. let mut arr = vec![1, 2, 3, 4, 5, 6];
65. cocktail_shaker_sort(&mut arr);
66. assert_eq!(arr, vec![1, 2, 3, 4, 5, 6]);
67. }
68. }