深蓝黑背景品牌封面：居中大标题「找数组里第 K 大的数」，副标题「快速选择：不排完，也能定位」；下方装饰——一排高低不一的数组柱条，中间一根基准柱被青色高亮，左侧三根较高的柱子染紫、右侧三根较矮的柱子为灰蓝，示意按基准分区；顶部标注「经典题解析 · 算法」与「Day 07 · 09-25」 图 1：本文封面，点明题目与「不排完也能定位」的主线。

先说明属性：这是一篇经典题解析，题目出自本地历史面试资料（见文末来源说明），与任何公司的当前招聘无关。「数组里第 K 大的元素」几乎人人都会第一反应「排序再取」，面试官真正想听的是后半句：能不能不排完？

想象面试现场，面试官写下：给定无序数组和整数 k，返回第 k 大的元素；追问——比 O(n log n) 更好能做到吗？

第一步，审题：先立正确性基准。

排序后取第 k 个，时间 O(n log n)、空间看排序实现，这个答案必须先说——它是你的正确性兜底，也是衬托更优解的背景板。然后点破关键观察：排序把 n 个元素的名次全部算出来了，但我们只要其中一个名次。为一个问题付出 n 个问题的代价，浪费就在这里。真正的问题是：能不能只算出「第 k 大」这一个名次？

第二步，核心直觉：分区一次，名次落一半。

借快排的分区操作：随机挑一个基准，把比它大的挪到左边、比它小的挪到右边。分区结束后，基准元素的位置就是它的最终名次——左边恰好有 p 个比它大的数，它就是第 p+1 大。于是目标名次落在左边就只在左半区继续找，落在右边就只在右半区继续找，另一半直接扔掉。每一轮问题规模大约减半，总比较次数约 n + n/2 + n/4，加起来不超过 2n，平均时间复杂度 O(n)。

这就是快速选择（quickselect）：快排的分区，加上「只进一半」的贪心。

第三步，两个必须交代的细节。

一，最坏情况是 O(n²)——每次基准都恰好是最值，规模只减一。工程上的标准解法是随机选基准，让最坏情况成为概率事件而非输入事件；对已有序的输入尤其重要。二，「第 k 大」默认按去重后的名次理解还是按下标理解，面试时要先问清。下面的实现按「排序后下标」理解，允许重复值占名次。

过程图：第一轮——数组 5 2 9 1 7 3 8 选 7 作基准，分区后左边 9、8 比它大，右边 5、2、1、3 比它小，基准正好是第 3 大；要找第 2 大，只在左半区 9、8 里继续。第二轮——对 9、8 再分区，基准 9 左边没有元素，它是左半区第 1 大，于是 8 就是全局第 2 大。每一轮问题规模大约减半，总比较次数约 n + n/2 + n/4 ≈ 2n。下方对比条：全排序 O(n log n) 排序后再取第 K 个；快速选择平均 O(n) 只处理一半又一半；注意最坏情况 O(n²)，随机选基准可规避 图 2：两轮分区定位第 2 大，以及全排序与快速选择的复杂度对比。

第四步，写出可运行的代码。

下面这份实现包含随机基准的快速选择与全排序复核，用 Node.js 22.15.0 直接运行（node quickselect.js）即可：

'use strict';

// 快速选择：在未完全排序的数组上找第 k 大（k 从 1 开始）
function quickSelect(nums, k) {
  const arr = [...nums];
  const target = arr.length - k; // 第 k 大 = 升序下标 length - k
  let lo = 0;
  let hi = arr.length - 1;
  while (lo <= hi) {
    const p = partition(arr, lo, hi);
    if (p === target) return arr[p];
    if (p < target) lo = p + 1;
    else hi = p - 1;
  }
  return undefined; // k 越界时兜底
}

// Lomuto 分区：随机取基准换到末尾，把比基准小的挪到左边，返回基准最终位置
function partition(arr, lo, hi) {
  const r = lo + Math.floor(Math.random() * (hi - lo + 1)); // 随机选基准，规避最坏情况
  [arr[r], arr[hi]] = [arr[hi], arr[r]];
  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]];
  return i;
}

const cases = [
  { nums: [5, 2, 9, 1, 7, 3, 8], k: 2 },
  { nums: [3, 2, 1, 5, 6, 4], k: 2 },
  { nums: [3, 2, 3, 1, 2, 4, 5, 5, 6], k: 4 },
  { nums: [1], k: 1 },
  { nums: [7, 6, 5, 4, 3, 2, 1], k: 7 },
];
for (const { nums, k } of cases) {
  const fast = quickSelect(nums, k);
  const check = [...nums].sort((a, b) => b - a)[k - 1]; // 全排序复核
  console.log(`[${nums}] 第 ${k} 大 -> 快速选择 ${fast}，全排序复核 ${check}`);
  if (fast !== check) throw new Error('两种方法结果不一致');
}

实测输出如下：

[5,2,9,1,7,3,8] 第 2 大 -> 快速选择 8，全排序复核 8
[3,2,1,5,6,4] 第 2 大 -> 快速选择 5，全排序复核 5
[3,2,3,1,2,4,5,5,6] 第 4 大 -> 快速选择 4，全排序复核 4
[1] 第 1 大 -> 快速选择 1，全排序复核 1
[7,6,5,4,3,2,1] 第 7 大 -> 快速选择 1，全排序复核 1

五个用例两种方法全部一致，覆盖了重复元素、单元素、完全逆序三个边界。

易错点清单。

一，只会排序取第 k 个，讲不出「只算一个名次」的优化动机。二，分区后两半边都递归——那就退化成了快排，丢掉 O(n) 的核心。三，固定取首元素作基准，被有序输入打成 O(n²) 还不知道为什么。四，k 与下标的换算搞错——第 k 大对应升序下标 length 减 k，写反了结果全错。五，不与面试官确认重复元素的口径。

回到面试现场，建议的答题节奏：先给排序法作为基准并指出浪费，再讲「分区一次名次落一半」的直觉，然后写出循环版快速选择，最后主动交代最坏情况与随机基准。top-k 采样、粗排选候选、实时榜单，背后都是这同一个「部分选择代替全排序」的思想。

如果面试官把题目改成「数据流里持续求第 K 大，数组会无限增长」，快速选择还合用吗？你会换成什么结构？欢迎写出你的思路。

参考资料

  • Node.js v22.x 官方 API 文档（文中代码运行环境为 Node.js 22.15.0，Array.prototype.sort、解构赋值等行为以此为准） — https://nodejs.org/docs/latest-v22.x/api/