快速排序

  1. pub fn quick_sort<T: PartialOrd>(arr: &mut [T]) {
  2.     if arr.len() > 1 {
  3.         quick_sort_range(arr, 0, arr.len() - 1);
  4.     }
  5. }
  7. fn quick_sort_range<T: PartialOrd>(arr: &mut [T], lo: usize, hi: usize) {
  8.     // 只有当元素个数大于一时才进行排序
  9.     if lo < hi {
  10.         let pos = partition(arr, lo, hi);
  11.         // let pos = partition_random(arr, lo, hi);
  12.         if pos != 0 {
  13.             // 如果 pos == 0, pos - 1 会发生溢出错误
  14.             quick_sort_range(arr, lo, pos - 1);
  15.         }
  16.         quick_sort_range(arr, pos + 1, hi);
  17.     }
  18. }
  20. fn partition<T: PartialOrd>(arr: &mut [T], lo: usize, hi: usize) -> usize {
  21.     // 默认选取 lo 作为 pivot
  22.     let pivot = lo;
  24.     let (mut left, mut right) = (lo, hi);
  25.     while left < right {
  26.         // 找到右边第一个不大于等于 arr[pivot] 的元素
  27.         while left < right && arr[right] >= arr[pivot] {
  28.             right -= 1;
  29.         }
  31.         // 找到左边第一个不小于等于 arr[pivot] 的元素
  32.         while left < right && arr[left] <= arr[pivot] {
  33.             left += 1;
  34.         }
  36.         // 交换前面找到的两个元素
  37.         if left != right {
  38.             arr.swap(left, right);
  39.         }
  40.     }
  42.     arr.swap(pivot, left);
  44.     // 返回正确的分割位置
  45.     left
  46. }
  48. // 随机选取 pivot 的位置
  49. fn partition_random<T: PartialOrd>(arr: &mut [T], lo: usize, hi: usize) -> usize {
  50.     // 在 Cargo.toml 的依赖中添加 rand 库
  51.     use rand::Rng;
  52.     let mut rng = rand::thread_rng();
  53.     let pivot = rng.gen_range(lo..=hi);
  55.     // 交换 lo 和 pivot 位置上的元素，从而间接使得 pivot = lo
  56.     // 因此后序操作和 partition() 函数一致
  57.     arr.swap(lo, pivot);
  59.     let pivot = lo;
  60.     let (mut left, mut right) = (lo, hi);
  61.     while left < right {
  62.         // 找到右边第一个不大于等于 arr[pivot] 的元素
  63.         while left < right && arr[right] >= arr[pivot] {
  64.             right -= 1;
  65.         }
  67.         // 找到左边第一个不小于等于 arr[pivot] 的元素
  68.         while left < right && arr[left] <= arr[pivot] {
  69.             left += 1;
  70.         }
  72.         // 交换前面找到的两个元素
  73.         if left != right {
  74.             arr.swap(left, right);
  75.         }
  76.     }
  78.     arr.swap(pivot, left);
  80.     // 返回正确的分割位置
  81.     left
  82. }
  84. #[cfg(test)]
  85. mod tests {
  86.     use super::*;
  88.     #[test]
  89.     fn test_empty_vec() {
  90.         let mut empty_vec: Vec<String> = vec![];
  91.         quick_sort(&mut empty_vec);
  92.         assert_eq!(empty_vec, Vec::<String>::new());
  93.     }
  95.     #[test]
  96.     fn test_number_vec() {
  97.         let mut vec = vec![7, 49, 73, 58, 30, 72, 44, 78, 23, 9];
  98.         quick_sort(&mut vec);
  99.         assert_eq!(vec, vec![7, 9, 23, 30, 44, 49, 58, 72, 73, 78]);
  100.     }
  102.     #[test]
  103.     fn test_string_vec() {
  104.         let mut vec = vec![
  105.             String::from("Bob"),
  106.             String::from("David"),
  107.             String::from("Carol"),
  108.             String::from("Alice"),
  109.         ];
  110.         quick_sort(&mut vec);
  111.         assert_eq!(
  112.             vec,
  113.             vec![
  114.                 String::from("Alice"),
  115.                 String::from("Bob"),
  116.                 String::from("Carol"),
  117.                 String::from("David"),
  118.             ]
  119.         );
  120.     }
  121. }