快速选择算法通过三路划分定位第k大数原始下标：先构建值-下标配对数组，将target_pos转为n-k升序索引，递归划分后根据k与等于pivot区间[lt,gt]关系决定返回或继续搜索。

用C++实现快速选择算法定位第K大数值在原数组中的下标位置，需在分区过程中保留原始索引映射关系，不能只对值排序后取下标——否则无法区分重复值或保持位置一致性。

构建带索引的值-下标配对数组

定义 vector<pair int>></pair> 类型容器，将每个元素的值和原始下标一起存入，例如 {nums[i], i}。

这一步不可省略：若仅排序数值，遇到重复值（如 [3,3,3,1] 中第2大是3，但有三个可能下标）将无法唯一确定原始位置。

实现三路划分的快速选择主逻辑

方法一：递归版本（推荐初学理解）

① 设当前处理区间为 [left, right]，随机选取一个 pivot 值（推荐用 nums[rand() % (right - left + 1) + left] 避免最坏退化）；

② 执行三路划分：将配对数组分为 pivot 三段，返回等于 pivot 的左右边界 lt 和 gt；

C++ Code Review Master

组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

③ 若 k 且 <code>k >= lt，说明第K大值就落在等于 pivot 的区间内，直接返回任一该区间内配对的原始下标（如 arr[lt].second）；

④ 否则根据K与区间边界关系，递归进入左段（k ）或右段（<code>k > gt）继续查找。

注意：K 是“第K大”，对应升序排列后的下标为 n - k，所以初始调用时传入的 target_pos = 【n - k】（0-based），不是 k 本身。

完整可运行源码

#include
#include
#include
#include
using namespace std;

int quickSelectIndex(vector& nums, int k) {
  int n = nums.size();
  vector> arr;
  for (int i = 0; i   int target_pos = n - k; // 转为升序下标
  return quickSelectHelper(arr, 0, n - 1, target_pos);
}

int quickSelectHelper(vector>& arr, int left, int right, int k) {
  if (left == right) return arr[left].second;
  default_random_engine gen;
  uniform_int_distribution dis(left, right);
  int pivot_idx = dis(gen);
  swap(arr[pivot_idx], arr[right]);
  int pivot_val = arr[right].first;
  int lt = left, gt = right, i = left;
  while (i     if (arr[i].first     else if (arr[i].first > pivot_val) swap(arr[i], arr[gt--]);
    else ++i;
  }
  if (k = lt) return arr[k].second;
  else if (k   else return quickSelectHelper(arr, gt + 1, right, k);
}

C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！