归并排序

1. pub fn merge_sort<T>(arr: &mut [T])
2. where
3. T: PartialOrd + Clone + Default,
4. {
5. if arr.len() > 1 {
6. merge_sort_range(arr, 0, arr.len() - 1);
7. }
8. }

10. fn merge_sort_range<T>(arr: &mut [T], lo: usize, hi: usize)
11. where
12. T: PartialOrd + Clone + Default,
13. {
14. // 只有当元素个数大于一时才进行排序
15. if lo < hi {
16. let mid = lo + ((hi - lo) >> 1);
17. merge_sort_range(arr, lo, mid);
18. merge_sort_range(arr, mid + 1, hi);
19. merge_two_arrays(arr, lo, mid, hi);
20. }
21. }

23. // 合并两个有序数组: arr[lo..=mid], arr[mid + 1..=hi]
24. fn merge_two_arrays<T>(arr: &mut [T], lo: usize, mid: usize, hi: usize)
25. where
26. T: PartialOrd + Clone + Default,
27. {
28. // 这里需要 clone 数组元素
29. let mut arr1 = arr[lo..=mid].to_vec();
30. let mut arr2 = arr[mid + 1..=hi].to_vec();

32. let (mut i, mut j) = (0, 0);
33. while i < arr1.len() && j < arr2.len() {
34. if arr1[i] < arr2[j] {
35. arr[i + j + lo] = std::mem::take(&mut arr1[i]);
36. i += 1;
37. } else {
38. arr[i + j + lo] = std::mem::take(&mut arr2[j]);
39. j += 1;
40. }
41. }

43. while i < arr1.len() {
44. arr[i + j + lo] = std::mem::take(&mut arr1[i]);
45. i += 1;
46. }

48. while j < arr2.len() {
49. arr[i + j + lo] = std::mem::take(&mut arr2[j]);
50. j += 1;
51. }
52. }

54. #[cfg(test)]
55. mod tests {
56. use super::*;

58. #[test]
59. fn test_empty_vec() {
60. let mut empty_vec: Vec<String> = vec![];
61. merge_sort(&mut empty_vec);
62. assert_eq!(empty_vec, Vec::<String>::new());
63. }

65. #[test]
66. fn test_number_vec() {
67. let mut vec = vec![7, 49, 73, 58, 30, 72, 44, 78, 23, 9];
68. merge_sort(&mut vec);
69. assert_eq!(vec, vec![7, 9, 23, 30, 44, 49, 58, 72, 73, 78]);
70. }

72. #[test]
73. fn test_string_vec() {
74. let mut vec = vec![
75. String::from("Bob"),
76. String::from("David"),
77. String::from("Carol"),
78. String::from("Alice"),
79. ];
80. merge_sort(&mut vec);
81. assert_eq!(
82. vec,
83. vec![
84. String::from("Alice"),
85. String::from("Bob"),
86. String::from("Carol"),
87. String::from("David"),
88. ]
89. );
90. }
91. }