臭皮匠排序

  1. fn _stooge_sort<T: Ord>(arr: &mut [T], start: usize, end: usize) {
  2.     if arr[start] > arr[end] {
  3.         arr.swap(start, end);
  4.     }
  6.     if start + 1 >= end {
  7.         return;
  8.     }
  10.     let k = (end - start + 1) / 3;
  12.     _stooge_sort(arr, start, end - k);
  13.     _stooge_sort(arr, start + k, end);
  14.     _stooge_sort(arr, start, end - k);
  15. }
  17. pub fn stooge_sort<T: Ord>(arr: &mut [T]) {
  18.     let len = arr.len();
  19.     if len == 0 {
  20.         return;
  21.     }
  23.     _stooge_sort(arr, 0, len - 1);
  24. }
  26. #[cfg(test)]
  27. mod test {
  28.     use super::*;
  30.     #[test]
  31.     fn basic() {
  32.         let mut vec = vec![3, 5, 6, 3, 1, 4];
  33.         stooge_sort(&mut vec);
  34.         for i in 0..vec.len() - 1 {
  35.             assert!(vec[i] <= vec[i + 1]);
  36.         }
  37.     }
  39.     #[test]
  40.     fn empty() {
  41.         let mut vec: Vec<i32> = vec![];
  42.         stooge_sort(&mut vec);
  43.         assert_eq!(vec, vec![]);
  44.     }
  46.     #[test]
  47.     fn reverse() {
  48.         let mut vec = vec![6, 5, 4, 3, 2, 1];
  49.         stooge_sort(&mut vec);
  50.         for i in 0..vec.len() - 1 {
  51.             assert!(vec[i] <= vec[i + 1]);
  52.         }
  53.     }
  55.     #[test]
  56.     fn already_sorted() {
  57.         let mut vec = vec![1, 2, 3, 4, 5, 6];
  58.         stooge_sort(&mut vec);
  59.         for i in 0..vec.len() - 1 {
  60.             assert!(vec[i] <= vec[i + 1]);
  61.         }
  62.     }
  63. }