快速排序

主要步骤

1. 快速排序主要分为三步：
   • 选择一个基准值（pivot）,这里简单实现选择数组最后1个元素
   • 根据选择的 pivot 将数组分为两部分：小于基准值的部分在 pivort 左边和大于基准值的部分在 pivot 右边
   • 再对分区后的这两部分进行递归再次排序

代码实现

TypeScript

function quickSort(nums: Array<number>, l: number, r: number) {
  if (l >= r) return

  // 1. 选择 pivot
  let pivot = nums[r]

  // 2. 根据 pivot 进行分区 
    // 1. 这里使用一个 idx 来标记循环结束后分区边界，及 idx 左边部分为小于 pivot 的元素，右边部分为大于 pivot 的元素
  let idx = l

  for (let i = l; i < r; i++) {
    if (nums[i] < pivot) {
      // 2. 如果当前元素小于 pivot，则交换 idx 和 i 的元素，并将 idx 向右移动一位
      [nums[idx], nums[i]] = [nums[i], nums[idx]]
      idx++
    }
  }
  
  // 3. 最后将 pivot 和 idx 的元素交换，完成分区
  [nums[idx], nums[r]] = [nums[r], nums[idx]]

  // 4. 递归处理分区后的数组
  quickSort(nums, l, idx - 1)
  quickSort(nums, idx + 1, r)
}

const nums = [3, 2, 1, 5, 4]
quickSort(nums, 0, nums.length - 1)
console.log(nums);

Rust

fn quick_sort(nums: &mut Vec<i32>, left: usize, right: usize) {
    if left >= right {
        return;
    }

    // 1. 选择 point
    let point = nums[right];

    // 2. 分区
    // idx 左边元素都小于 point
    let mut idx = left;

    // 从 left 到 right 遍历,不包含 right
    for i in left..right {
        if nums[i] < point {
            // 交换
            nums.swap(idx, i);
            idx += 1;
        }
    }
    nums.swap(idx, right);

    // 3. 递归
    if idx > 0 {
        // 防止 idx == 0时，idx-1 越界不为usize
        quick_sort(nums, left, idx - 1);
    }
    quick_sort(nums, idx + 1, right);
}

#[cfg(test)]
mod test {
    use super::quick_sort;
    #[test]
    fn test_quick_sort() {
        let mut nums = vec![3, 2, 1, 5, 4];
        let len = nums.len();
        quick_sort(&mut nums, 0, len - 1);
        assert_eq!(nums, vec![1, 2, 3, 4, 5]);
    }
}