插入排序

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