简介

对数组 nums 排序，快排的方法是现在nums随机选择一个数字 x，然后将比 x 小的放到数组左边，比x大的放到数组右边。然后对左右两边分别递归。

效率

  • 时间复杂度：快速排序 - 图1
  • 空间复杂度：快速排序 - 图2

  • 稳定性：不稳定

    实现

    分组代码：

    1. use rand::{thread_rng, Rng};
    2. // 对nums进行分组，并返回分组后中间元素的位置
    3. fn partition(nums: &mut [i32]) -> usize{
    4.   if nums.len() <= 0 {
    5.       panic!("array contains no elements");
    6.   }
    8.   // 随机选择一个元素x
    9.   let index = thread_rng().gen_range(0, nums.len());
    10.   let end = nums.len() - 1;
    11.   // 将选择的元素x先换到最后
    12.   nums.swap(index, end);
    14.   // small 表示下一个比选中的数x小的数该放的位置，递增的
    15.   let mut small = 0;
    16.   for i in 0..nums.len()-1{
    17.       // 遇到比选中元素x小的，替换到small位置，small前进一位
    18.       if nums[i] < nums[end] {
    19.           nums.swap(small, i);
    20.           small += 1;
    21.       } 
    22.   }
    24.   // 此时比x小的在[0,small)，比x大的在[small,end),x在[end]
    25.   // 将x换到small，此时比x小的在[0,small)，x在[small], 比x大的在(small,end]
    26.   nums.swap(small, end);
    28.   small
    29. }

快排代码：

  1. fn quick_sort(nums: &mut [i32]) {
  2.     if nums.len() <= 1 {
  3.         return;
  4.     }
  6.     let split_index = partition(nums);
  7.     quick_sort(&mut nums[0..split_index]);
  8.     let end = nums.len();
  9.     quick_sort(&mut nums[split_index + 1..end]);
  10. }