插入排序

1. pub fn insertion_sort<T: PartialOrd>(arr: &mut [T]) {
2. // 从第二个元素开始排序
3. for i in 1..arr.len() {
4. // 找到 arr[i] 该插入的位置
5. let mut j = i;
6. while j > 0 && arr[j - 1] > arr[j] {
7. arr.swap(j - 1, j);
8. j -= 1;
9. }
10. }
11. }

13. // 这里需要 T: Ord 是因为 binary_search() 方法的限制
14. pub fn insertion_sort_binary_search<T: Ord>(arr: &mut[T]) {
15. // 从第二个元素开始排序
16. for i in 1..arr.len() {
17. // 利用二分查找获取 arr[i] 应该插入的位置
18. let pos = arr[..i].binary_search(&arr[i]).unwrap_or_else(|pos| pos);
19. let mut j = i;
20. while j > pos {
21. arr.swap(j - 1, j);
22. j -= 1;
23. }
24. }
25. }

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

31. mod insertion_sort {
32. use super::*;

34. #[test]
35. fn test_empty_vec() {
36. let mut empty_vec: Vec<String> = vec![];
37. insertion_sort(&mut empty_vec);
38. assert_eq!(empty_vec, Vec::<String>::new());
39. }

41. #[test]
42. fn test_number_vec() {
43. let mut vec = vec![7, 49, 73, 58, 30, 72, 44, 78, 23, 9];
44. insertion_sort(&mut vec);
45. assert_eq!(vec, vec![7, 9, 23, 30, 44, 49, 58, 72, 73, 78]);
46. }

48. #[test]
49. fn test_string_vec() {
50. let mut vec = vec![
51. String::from("Bob"),
52. String::from("David"),
53. String::from("Carol"),
54. String::from("Alice"),
55. ];
56. insertion_sort(&mut vec);
57. assert_eq!(
58. vec,
59. vec![
60. String::from("Alice"),
61. String::from("Bob"),
62. String::from("Carol"),
63. String::from("David"),
64. ]
65. );
66. }
67. }

69. mod insertion_sort_binary_search {
70. use super::*;

72. #[test]
73. fn test_empty_vec() {
74. let mut empty_vec: Vec<String> = vec![];
75. insertion_sort_binary_search(&mut empty_vec);
76. assert_eq!(empty_vec, Vec::<String>::new());
77. }

79. #[test]
80. fn test_number_vec() {
81. let mut vec = vec![7, 49, 73, 58, 30, 72, 44, 78, 23, 9];
82. insertion_sort_binary_search(&mut vec);
83. assert_eq!(vec, vec![7, 9, 23, 30, 44, 49, 58, 72, 73, 78]);
84. }

86. #[test]
87. fn test_string_vec() {
88. let mut vec = vec![
89. String::from("Bob"),
90. String::from("David"),
91. String::from("Carol"),
92. String::from("Alice"),
93. ];
94. insertion_sort_binary_search(&mut vec);
95. assert_eq!(
96. vec,
97. vec![
98. String::from("Alice"),
99. String::from("Bob"),
100. String::from("Carol"),
101. String::from("David"),
102. ]
103. );
104. }
105. }
106. }