查找第 k 小元素的快速选择

功能说明

该示例实现 quickselect，用于在无需完整排序的情况下找到第 k 小元素，例如计算中位数、取排行榜阈值或分位数。k 从零开始，必须落在数组下标范围内。算法在输入副本上操作，因此调用方数据保持不变。平均时间复杂度为线性，最坏情况为平方，随机枢轴显著降低遭遇极端输入的概率。

关键代码

函数先校验数组、k 与随机函数，再复制数组。每轮在当前区间内随机选一个枢轴并换到右端，使用 Lomuto 划分把所有小于枢轴的元素移到左侧，记录最终枢轴位置。若位置正好等于 k 直接返回；小于 k 则丢弃左半部分，大于 k 则丢弃右半部分。随机数会校验是否落在零到一之间，防止错误的随机源导致下标越界。循环结束时区间收缩为单点，返回该值。

使用注意

Lomuto 划分对大量重复元素会退化为平方时间，数据重复度高时可改用三路划分。k 是零基下标，第 1 小对应 k 等于零，业务层不要混淆。随机源可注入以便测试，但必须返回小于一的非负数。函数返回元素值而不是下标，也不保证相等元素的相对顺序。输入为空时任何 k 都非法。

验证方式

用固定随机源对乱序数组测试 k 为零、中间与末尾，结果应与完整排序后的对应下标一致；对含大量重复值的数组验证返回值正确；断言输入数组在调用后保持不变；测试 k 为负数、越界、小数，以及 random 返回一或负数时分别抛 RangeError；空数组应抛 RangeError。

代码示例

function swap(values, left, right) {
  const temporary = values[left];
  values[left] = values[right];
  values[right] = temporary;
}

export function quickselect(values, k, options = {}) {
  if (!Array.isArray(values)) throw new TypeError("values must be an array");
  if (!Number.isInteger(k) || k < 0 || k >= values.length) {
    throw new RangeError("k must be an integer within the array bounds");
  }
  const random = options.random ?? Math.random;
  if (typeof random !== "function") throw new TypeError("random must be a function");

  const data = values.slice();
  let left = 0;
  let right = data.length - 1;

  while (left < right) {
    const sample = random();
    if (!(sample >= 0 && sample < 1)) {
      throw new RangeError("random must return a value in [0, 1)");
    }
    const pivotIndex = left + Math.floor(sample * (right - left + 1));
    swap(data, pivotIndex, right);
    const pivot = data[right];
    let store = left;
    for (let index = left; index < right; index += 1) {
      if (data[index] < pivot) {
        swap(data, store, index);
        store += 1;
      }
    }
    swap(data, store, right);
    if (store === k) return data[store];
    if (store < k) left = store + 1;
    else right = store - 1;
  }
  return data[left];
}