归并排序

  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. }