用快速选择找第 K 大元素

概述

用快速选择找第 K 大元素：以平均线性时间用快速选择算法找出第 K 大元素，在只需一个排名时避免完整排序的开销。

解决什么问题

本示例演示如何用 JavaScript 实现「用快速选择找第 K 大元素」。它聚焦一个具体且可复用的技术要点，把完整实现与必要说明放在一起，读者可以直接复制使用，也可以据此理解背后的设计思路与取舍。示例刻意保持职责单一，避免把多个无关功能揉进同一段代码，从而降低理解与复用成本。

核心思路

代码在进入核心逻辑前先做输入与边界检查，对非法参数提前返回或抛出明确错误，避免错误状态在下游扩散。核心处理部分尽量保持清晰、可预测，把校验、计算与状态变更分离，使逻辑更易于测试和推演。对于可能失败或耗时的操作，示例显式处理失败路径并给出清晰的错误信息，而不是让异常静默吞没，从而缩短排查时间。

适用场景

本示例适用于以下场景：数据一致性与转换。在实际项目中，应根据真实负载与输入规模调整参数与容量，关注边界条件与并发情形下的行为，并用单元测试或集成测试锁定预期结果，防止后续修改悄然改变行为。

注意事项

把示例用于生产环境时，应结合团队的编码规范、错误处理约定与可观测性要求加以调整。例如补充结构化日志以便追踪，明确超时与重试策略以提升健壮性，并对用户输入做必要校验以满足安全边界要求。理解示例背后的原理，往往比直接复制代码更重要，因为需求变化时通常需要对参数与结构做出调整。

代码示例

export function kthLargest(items, k) {
  if (k < 1 || k > items.length) throw new RangeError("k out of range");
  const target = items.length - k;
  const data = items.slice();
  let left = 0;
  let right = data.length - 1;
  while (true) {
    const pivotIndex = partition(data, left, right);
    if (pivotIndex === target) return data[pivotIndex];
    if (pivotIndex < target) left = pivotIndex + 1;
    else right = pivotIndex - 1;
  }
}

function partition(data, left, right) {
  const pivot = data[right];
  let store = left;
  for (let i = left; i < right; i++) {
    if (data[i] < pivot) {
      [data[i], data[store]] = [data[store], data[i]];
      store++;
    }
  }
  [data[right], data[store]] = [data[store], data[right]];
  return store;
}