梳排序

  1. pub fn comb_sort<T: Ord>(arr: &mut [T]) {
  2.     let mut gap = arr.len();
  3.     let shrink = 1.3;
  4.     let mut sorted = false;
  6.     while !sorted {
  7.         gap = (gap as f32 / shrink).floor() as usize;
  8.         if gap <= 1 {
  9.             gap = 1;
  10.             sorted = true;
  11.         }
  12.         for i in 0..arr.len() - gap {
  13.             let j = i + gap;
  14.             if arr[i] > arr[j] {
  15.                 arr.swap(i, j);
  16.                 sorted = false;
  17.             }
  18.         }
  19.     }
  20. }
  22. #[cfg(test)]
  23. mod tests {
  24.     use super::*;
  26.     #[test]
  27.     fn descending() {
  28.         //descending
  29.         let mut ve1 = vec![6, 5, 4, 3, 2, 1];
  30.         comb_sort(&mut ve1);
  31.         for i in 0..ve1.len() - 1 {
  32.             assert!(ve1[i] <= ve1[i + 1]);
  33.         }
  34.     }
  36.     #[test]
  37.     fn ascending() {
  38.         //pre-sorted
  39.         let mut ve2 = vec![1, 2, 3, 4, 5, 6];
  40.         comb_sort(&mut ve2);
  41.         for i in 0..ve2.len() - 1 {
  42.             assert!(ve2[i] <= ve2[i + 1]);
  43.         }
  44.     }
  45. }