希尔排序

  1. pub fn shell_sort<T: Ord + Copy>(values: &mut Vec<T>) {
  2.     // shell sort works by swiping the value at a given gap and decreasing the gap to 1
  3.     fn insertion<T: Ord + Copy>(values: &mut Vec<T>, start: usize, gap: usize) {
  4.         for i in ((start + gap)..values.len()).step_by(gap) {
  5.             let val_current = values[i];
  6.             let mut pos = i;
  7.             // make swaps
  8.             while pos >= gap && values[pos - gap] > val_current {
  9.                 values[pos] = values[pos - gap];
  10.                 pos -= gap;
  11.             }
  12.             values[pos] = val_current;
  13.         }
  14.     }
  16.     let mut count_sublist = values.len() / 2; // makes gap as long as half of the array
  17.     while count_sublist > 0 {
  18.         for pos_start in 0..count_sublist {
  19.             insertion(values, pos_start, count_sublist);
  20.         }
  21.         count_sublist /= 2; // makes gap as half of previous
  22.     }
  23. }
  25. #[cfg(test)]
  26. mod test {
  27.     use super::shell_sort;
  29.     #[test]
  30.     fn basic() {
  31.         let mut vec = vec![3, 5, 6, 3, 1, 4];
  32.         shell_sort(&mut vec);
  33.         for i in 0..vec.len() - 1 {
  34.             assert!(vec[i] <= vec[i + 1]);
  35.         }
  36.     }
  38.     #[test]
  39.     fn empty() {
  40.         let mut vec: Vec<i32> = vec![];
  41.         shell_sort(&mut vec);
  42.         assert_eq!(vec, vec![]);
  43.     }
  45.     #[test]
  46.     fn reverse() {
  47.         let mut vec = vec![6, 5, 4, 3, 2, 1];
  48.         shell_sort(&mut vec);
  49.         for i in 0..vec.len() - 1 {
  50.             assert!(vec[i] <= vec[i + 1]);
  51.         }
  52.     }
  54.     #[test]
  55.     fn already_sorted() {
  56.         let mut vec = vec![1, 2, 3, 4, 5, 6];
  57.         shell_sort(&mut vec);
  58.         for i in 0..vec.len() - 1 {
  59.             assert!(vec[i] <= vec[i + 1]);
  60.         }
  61.     }
  62. }