鸡尾酒排序

  1. pub fn cocktail_shaker_sort<T: Ord>(arr: &mut [T]) {
  2.     let len = arr.len();
  4.     if len == 0 {
  5.         return;
  6.     }
  8.     loop {
  9.         let mut swapped = false;
  11.         for i in 0..(len - 1).clamp(0, len) {
  12.             if arr[i] > arr[i + 1] {
  13.                 arr.swap(i, i + 1);
  14.                 swapped = true;
  15.             }
  16.         }
  18.         if !swapped {
  19.             break;
  20.         }
  22.         swapped = false;
  24.         for i in (0..(len - 1).clamp(0, len)).rev() {
  25.             if arr[i] > arr[i + 1] {
  26.                 arr.swap(i, i + 1);
  27.                 swapped = true;
  28.             }
  29.         }
  31.         if !swapped {
  32.             break;
  33.         }
  34.     }
  35. }
  37. #[cfg(test)]
  38. mod tests {
  39.     use super::*;
  41.     #[test]
  42.     fn basic() {
  43.         let mut arr = vec![5, 2, 1, 3, 4, 6];
  44.         cocktail_shaker_sort(&mut arr);
  45.         assert_eq!(arr, vec![1, 2, 3, 4, 5, 6]);
  46.     }
  48.     #[test]
  49.     fn empty() {
  50.         let mut arr = Vec::<i32>::new();
  51.         cocktail_shaker_sort(&mut arr);
  52.         assert_eq!(arr, vec![]);
  53.     }
  55.     #[test]
  56.     fn one_element() {
  57.         let mut arr = vec![1];
  58.         cocktail_shaker_sort(&mut arr);
  59.         assert_eq!(arr, vec![1]);
  60.     }
  62.     #[test]
  63.     fn pre_sorted() {
  64.         let mut arr = vec![1, 2, 3, 4, 5, 6];
  65.         cocktail_shaker_sort(&mut arr);
  66.         assert_eq!(arr, vec![1, 2, 3, 4, 5, 6]);
  67.     }
  68. }