快速排序

快速排序如何工作？

• 分治: 先做哨兵划分, 再对左右子数组递归;
• 终止条件: 子数组长度小于等于 1;

哨兵划分如何工作？

• 取 nums[left] 作为基准数 base, 令 i = left, j = right;
• j 从右向左找首个小于 base 的元素;
• i 从左向右找首个大于 base 的元素;
• 交换这两个元素, 重复直到 i 与 j 相遇;
• 把 base 交换到相遇点 i;
• 结果: 左子数组 < base < 右子数组;

快速排序如何实现？

function quickSort(nums: number[], left: number, right: number): void {
  if (left >= right) return;
  const pivot = partition(nums, left, right);
  quickSort(nums, left, pivot - 1);
  quickSort(nums, pivot + 1, right);
}

function partition(nums: number[], left: number, right: number): number {
  let i = left;
  let j = right;
  while (i < j) {
    while (i < j && nums[j] >= nums[left]) j--;
    while (i < j && nums[i] <= nums[left]) i++;
    [nums[i], nums[j]] = [nums[j], nums[i]];
  }
  [nums[i], nums[left]] = [nums[left], nums[i]];
  return i;
}

快速排序的特性是什么？

• 时间复杂度: 平均 O(n log n), 最差 O(n^2);
• 空间复杂度: 递归栈平均 O(log n), 最差 O(n);
• 稳定性: 非稳定排序;

基准数为什么会劣化, 如何避免？

• 劣化原因: 输入已有序且基准数固定取端点时, 每次划分只能排除一个元素, 递归退化为链表;
• 方法一: 随机化基准数, 划分前把 nums[left] 与区间内随机下标交换, 期望接近中位数;
• 方法二: 三路划分, 把等于基准的元素集中成一段, 见 颜色分类;
• 方法三: 求第 k 大时只递归目标所在的一半, 见 第 K 个最大元素;