Timsort

算法由 xieyu567 提交

  1. use std::cmp::min;
  3. pub fn find_min_run(mut n: usize) -> usize {
  4.     let mut r = 0;
  5.     let minimum = 64;
  6.     while n >= minimum {
  7.         r |= n & 1;
  8.         n >>= 1;
  9.     }
  10.     n + r
  11. }
  13. pub fn insert_sort<T>(arr: &mut [T], left: usize, right: usize)
  14.     where T: PartialOrd + Copy, {
  15.     for i in left + 1..right + 1 {
  16.         let element = arr[i];
  17.         let mut j = i - 1;
  18.         while element < arr[j] && j >= left {
  19.             arr[j + 1] = arr[j];
  20.             j -= 1;
  21.         }
  22.         arr[j + 1] = element;
  23.     }
  24. }
  26. pub fn merge<T>(arr: &mut [T], left: usize, mid: usize, right: usize)
  27.     where T: PartialOrd + Copy, {
  28.     let array_length1 = mid - left + 1;
  29.     let array_length2 = right - mid;
  30.     let left_arr = Vec::from(&arr[left..left + array_length1]);
  31.     let right_arr = Vec::from(&arr[mid + 1..mid + 1 + array_length2]);
  33.     let (mut i, mut j, mut k) = (0, 0, left);
  34.     while j < array_length2 && i < array_length1 {
  35.         if left_arr[i] <= right_arr[j] {
  36.             arr[k] = left_arr[i];
  37.             i += 1;
  38.         } else {
  39.             arr[k] = right_arr[j];
  40.             j += 1
  41.         }
  42.         k += 1
  43.     }
  44.     while i < array_length1 {
  45.         arr[k] = left_arr[i];
  46.         k += 1;
  47.         i += 1
  48.     }
  49.     while j < array_length2 {
  50.         arr[k] = right_arr[j];
  51.         k += 1;
  52.         j += 1
  53.     }
  54. }
  56. pub fn tim_sort<T>(arr: &mut [T])
  57.     where T: PartialOrd + Copy, {
  58.     let n = arr.len();
  59.     let min_run = find_min_run(n);
  61.     for start in (0..n).filter(|x| x % min_run == 0) {
  62.         let end = min(start + min_run - 1, n - 1);
  63.         insert_sort(arr, start, end)
  64.     }
  65.     let mut size = min_run;
  66.     while size < n {
  67.         for left in (0..n).filter(|x| x % (2 * size) == 0) {
  68.             let mid = min(n - 1, left + size - 1);
  69.             let right = min(left + 2 * size - 1, n - 1);
  70.             merge(arr, left, mid, right)
  71.         }
  72.         size = 2 * size
  73.     }
  74. }
  76. #[cfg(test)]
  77. mod tests {
  78.     use super::*;
  80.     #[test]
  81.     fn cal_min() {
  82.         let n = 189;
  83.         let min_run = find_min_run(n);
  84.         assert_eq!(48, min_run);
  85.         assert_eq!(61, find_min_run(976));
  86.     }
  88.     #[test]
  89.     fn insert_test() {
  90.         let mut vec = vec![7, 49, 73, 58, 30, 72, 44, 78, 23, 9];
  91.         insert_sort(&mut vec, 0, 9);
  92.         assert_eq!(vec![7, 9, 23, 30, 44, 49, 58, 72, 73, 78], vec)
  93.     }
  95.     #[test]
  96.     fn tim_test() {
  97.         let mut vec = vec![7, 49, 73, 58, 30, 72, 44, 78, 23, 9];
  98.         tim_sort(&mut vec);
  99.         assert_eq!(vec, vec![7, 9, 23, 30, 44, 49, 58, 72, 73, 78]);
  100.     }
  101. }