快速排序

场景引入

如果只能掌握一种排序算法，应该选哪个？答案是快速排序。

快速排序是实际应用中最广泛使用的排序算法。C 语言标准库的 qsort、C++ 的 std::sort（结合插入排序和堆排序的 IntroSort）都以快速排序为核心。它的平均时间复杂度为 O(n log n)，且常数因子小、缓存友好，在大多数场景下都比归并排序和堆排序更快。

核心思路

快速排序同样基于分治思想，但与归并排序的策略相反：

• 归并排序：先递归分解，再合并（重点在"合"）
• 快速排序：先分区处理，再递归（重点在"分"）

算法步骤

1. 选择基准（Pivot）：从数组中选一个元素作为基准
2. 分区（Partition）：将数组重新排列，使得基准左边的元素都 <= 基准，右边的都 > 基准
3. 递归：对基准左右两部分分别递归排序

Partition 函数详解（Lomuto 方案）

Lomuto 分区方案以数组最后一个元素为基准：

1. 维护指针 i，指向"小于基准区间"的右边界
2. 用指针 j 从左到右扫描
3. 如果 arr[j] < pivot，将 arr[j] 与 arr[i] 交换，i++
4. 扫描完成后，将 pivot 放到 i 的位置

分区结束后，pivot 就在它最终排序后应该在的位置上。

算法流程图

可视化演示

加载可视化中...

代码实现

基础版本

function quickSort(arr, lo = 0, hi = arr.length - 1) {
  if (lo >= hi) return arr;

  // Lomuto 分区
  const pivot = arr[hi];
  let i = lo;
  for (let j = lo; j < hi; j++) {
    if (arr[j] < pivot) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
      i++;
    }
  }
  [arr[i], arr[hi]] = [arr[hi], arr[i]];

  quickSort(arr, lo, i - 1);
  quickSort(arr, i + 1, hi);
  return arr;
}

优化一：随机选择基准

固定选最后一个元素做基准，当数组已排序时会退化到 O(n²)。随机选基准可以避免：

function quickSortRandom(arr, lo = 0, hi = arr.length - 1) {
  if (lo >= hi) return arr;

  // 随机选基准，与最后一个元素交换
  const randIdx = lo + Math.floor(Math.random() * (hi - lo + 1));
  [arr[randIdx], arr[hi]] = [arr[hi], arr[randIdx]];

  const pivot = arr[hi];
  let i = lo;
  for (let j = lo; j < hi; j++) {
    if (arr[j] < pivot) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
      i++;
    }
  }
  [arr[i], arr[hi]] = [arr[hi], arr[i]];

  quickSortRandom(arr, lo, i - 1);
  quickSortRandom(arr, i + 1, hi);
  return arr;
}

优化二：三路分区

当数组中有大量重复元素时，标准分区效率很低。三路分区将数组分为三部分：< pivot、== pivot、> pivot：

function quickSort3Way(arr, lo = 0, hi = arr.length - 1) {
  if (lo >= hi) return arr;

  const pivot = arr[lo];
  let lt = lo;     // arr[lo..lt-1]  < pivot
  let gt = hi;     // arr[gt+1..hi]  > pivot
  let i = lo + 1;  // arr[lt..i-1]  == pivot

  while (i <= gt) {
    if (arr[i] < pivot) {
      [arr[lt], arr[i]] = [arr[i], arr[lt]];
      lt++;
      i++;
    } else if (arr[i] > pivot) {
      [arr[i], arr[gt]] = [arr[gt], arr[i]];
      gt--;
    } else {
      i++;
    }
  }

  quickSort3Way(arr, lo, lt - 1);
  quickSort3Way(arr, gt + 1, hi);
  return arr;
}

应用：快速选择（Quick Select）

利用 partition 的性质，可以在 O(n) 平均时间内找到第 K 大/小的元素，无需完整排序：

function findKthLargest(nums, k) {
  const target = nums.length - k; // 第 k 大 = 排序后下标 n-k

  function quickSelect(lo, hi) {
    const pivot = nums[hi];
    let i = lo;
    for (let j = lo; j < hi; j++) {
      if (nums[j] < pivot) {
        [nums[i], nums[j]] = [nums[j], nums[i]];
        i++;
      }
    }
    [nums[i], nums[hi]] = [nums[hi], nums[i]];

    if (i === target) return nums[i];
    if (i < target) return quickSelect(i + 1, hi);
    return quickSelect(lo, i - 1);
  }

  return quickSelect(0, nums.length - 1);
}

复杂度分析

	时间复杂度	空间复杂度
最好	O(n log n) — 每次均匀分区	O(log n) 递归栈
平均	O(n log n)	O(log n)
最坏	O(n²) — 每次分区极端不均（已排序+固定基准）	O(n) 递归栈

稳定性：不稳定。分区过程中元素交换会改变相等元素的相对顺序。

为什么快速排序实际上比归并排序快？

• 缓存友好：快排在原数组上操作，内存访问连续；归并需要额外数组，缓存命中率低
• 常数因子小：分区操作比 merge 操作简单
• 尾递归优化：可以对较短的分区使用尾递归，减少栈深度

面试要点

• 手写 partition 函数是面试核心考点
• 理解为什么最坏情况是 O(n²)，以及如何用随机化避免
• 三路分区解决重复元素问题（LC 75 颜色分类就是三路分区的应用）
• Quick Select 是面试高频题，掌握从快排到快速选择的推导

LeetCode 练习

• LC 912. 排序数组 — 快排标准实现（注意随机化，否则会超时）
• LC 215. 数组中的第 K 个最大元素 — Quick Select 经典应用
• LC 75. 颜色分类 — 三路分区的直接应用
• LC 347. 前 K 个高频元素 — 可用 Quick Select 求解