冒泡排序

  1. pub fn bubble_sort<T: PartialOrd>(arr: &mut [T]) {
  2.     if arr.len() <= 1 {
  3.         return;
  4.     }
  6.     let size = arr.len();
  7.     for i in 0..(size - 1) {
  8.         // 标记当前循环是否发生元素交换
  9.         let mut swapped = false;
  11.         // 最后i个元素已经排好了顺序
  12.         for j in 1..(size - i) {
  13.             if arr[j - 1] > arr[j] { 
  14.                 arr.swap(j - 1, j);
  15.                 swapped = true;
  16.             }
  17.         }
  19.         // 如果当前循环没有发生元素交换，说明数组已经有序
  20.         if !swapped {
  21.             break;
  22.         }
  23.     }
  24. }
  26. #[cfg(test)]
  27. mod tests {
  28.     use super::*;
  30.     #[test]
  31.     fn test_empty_vec() {
  32.         let mut empty_vec: Vec<String> = vec![];
  33.         bubble_sort(&mut empty_vec);
  34.         assert_eq!(empty_vec, Vec::<String>::new());
  35.     }
  37.     #[test]
  38.     fn test_number_vec() {
  39.         let mut vec = vec![7, 49, 73, 58, 30, 72, 44, 78, 23, 9];
  40.         bubble_sort(&mut vec);
  41.         assert_eq!(vec, vec![7, 9, 23, 30, 44, 49, 58, 72, 73, 78]);
  42.     }
  44.     #[test]
  45.     fn test_string_vec() {
  46.         let mut vec = vec![
  47.             String::from("Bob"),
  48.             String::from("David"),
  49.             String::from("Carol"),
  50.             String::from("Alice"),
  51.         ];
  52.         bubble_sort(&mut vec);
  53.         assert_eq!(
  54.             vec,
  55.             vec![
  56.                 String::from("Alice"),
  57.                 String::from("Bob"),
  58.                 String::from("Carol"),
  59.                 String::from("David"),
  60.             ]
  61.         );
  62.     }
  63. }