快排

直接看代码：
有四个注意点：

  1. leetcode上rand库不好用，不知道究竟输入是啥
  2. 在进入左问题的过程中会出现溢出，因为lt是uszie要进行处理
  3. while中应该是小于gt，这样才能省略额外空间，对应的，最后的右问题区间也是[gt, r]

  4. 就是大于的时候要注意，没有i+1

    1. pub fn sort_array(mut nums: Vec<i32>) -> Vec<i32> {
    2.  let len = nums.len();
    3.  partition(&mut nums, 0, len - 1);
    4.  nums
    5. }
    6. fn partition(nums: &mut Vec<i32>, l: usize, r: usize) {
    7.  if l>=r {
    8.      return;
    9.  }
    10.  // 获取随机的pivot
    11.  let pivot_index = rand::thread_rng().gen_range(l..=r);
    12.  let pivot = nums[pivot_index];
    13.  nums.swap(pivot_index, l);
    15.  let mut lt = l;
    16.  let mut gt = r + 1;
    17.  let mut i = l + 1;
    18.  // 注意是小于gt，不然重复了
    19.  while i < gt {
    20.      // 小于的数放在pivot左边
    21.      if nums[i] < pivot && lt < r{
    22.          lt += 1;
    23.          nums.swap(lt, i);
    24.          i += 1;
    25.      }
    26.      else if nums[i] == pivot {
    27.          i += 1;
    28.      } else {
    29.          // 注意这个特殊情况，可能换过来还是大
    30.          gt -= 1;
    31.          nums.swap(gt, i);
    32.      }
    33.  }
    34.  nums.swap(lt, l);
    35.  let lt = match lt.checked_sub(1)  {
    36.      None => 0,
    37.      Some(x) => x
    38.  };
    39.  partition(nums, l, lt);
    40.  // 使用gt的目的
    41.  partition(nums, gt, r);
    42. }

闭包——虚表
pin——自引用问题——协作式绿色线程调度