地精排序

  1. use std::cmp;
  3. pub fn gnome_sort<T>(arr: &[T]) -> Vec<T>
  4. where
  5.     T: cmp::PartialEq + cmp::PartialOrd + Clone,
  6. {
  7.     let mut arr = arr.to_vec();
  8.     let mut i: usize = 1;
  9.     let mut j: usize = 2;
  11.     while i < arr.len() {
  12.         if arr[i - 1] < arr[i] {
  13.             i = j;
  14.             j = i + 1;
  15.         } else {
  16.             arr.swap(i - 1, i);
  17.             i -= 1;
  18.             if i == 0 {
  19.                 i = j;
  20.                 j += 1;
  21.             }
  22.         }
  23.     }
  24.     arr
  25. }
  27. #[cfg(test)]
  28. mod tests {
  29.     use super::*;
  31.     #[test]
  32.     fn basic() {
  33.         let res = gnome_sort(&vec![6, 5, -8, 3, 2, 3]);
  34.         assert_eq!(res, vec![-8, 2, 3, 3, 5, 6]);
  35.     }
  37.     #[test]
  38.     fn already_sorted() {
  39.         let res = gnome_sort(&vec!["a", "b", "c"]);
  40.         assert_eq!(res, vec!["a", "b", "c"]);
  41.     }
  43.     #[test]
  44.     fn odd_number_of_elements() {
  45.         let res = gnome_sort(&vec!["d", "a", "c", "e", "b"]);
  46.         assert_eq!(res, vec!["a", "b", "c", "d", "e"]);
  47.     }
  49.     #[test]
  50.     fn one_element() {
  51.         let res = gnome_sort(&vec![3]);
  52.         assert_eq!(res, vec![3]);
  53.     }
  55.     #[test]
  56.     fn empty() {
  57.         let res = gnome_sort(&Vec::<u8>::new());
  58.         assert_eq!(res, vec![]);
  59.     }
  60. }