快速选择算法通过维护值与原始下标绑定的pair数组，在分区过程中保持索引同步，将第k大问题转为求升序第n-k小元素的原始下标；每次lomuto划分后仅递归目标侧，最终返回对应原始下标。
用C++实现快速选择算法（QuickSelect）定位第K大数值在原数组中的下标位置，需在不完全排序的前提下高效收缩搜索范围，核心在于每次划分后仅递归处理含目标秩的一侧子区间。
理解第K大与数组下标的对应关系
第K大意味着升序排列后索引为 【n - K】 的元素（0-based），例如数组[3,2,1,5,4]中第2大是4，升序后为[1,2,3,4,5]，对应索引5−2=3。因此需将问题转为求升序第 【target_idx = n - K】 小的元素原始位置——不是值，而是它最初在arr[]里的下标。
必须同步维护原始下标信息，不能只对值排序后查位置，否则无法还原原始索引。
构造带索引绑定的可划分结构
定义 pair
这一步不可省略：若仅用值数组做partition，后续无法回溯原始位置；若每次靠值反查下标，重复扫描会导致复杂度退化为O(n²)。
实现Lomuto分区并保留原始下标映射
采用Lomuto分区方案，pivot选末尾元素，遍历中交换的是整个pair，确保值与下标始终绑定。
分区结束后，pivot最终落于位置pos，此时左侧所有元素 ≤ pivot，右侧 ≥ pivot（升序语义）。若pos == target_idx，直接返回pivot.second；若pos > target_idx，递归左半段；否则递归右半段（不含pivot）。
注意：右半段递归时起始下标为pos+1，不能包含pivot位置，否则可能死循环。
完整C++源码
#include
#include
using namespace std;
int quickSelectIndex(vector
int n = nums.size();
int target_idx = n - k; // 升序第target_idx小（0-based）
vector
for (int i = 0; i arr_idx.emplace_back(nums[i], i);
int left = 0, right = n - 1;
while (left int pivot_idx = left + rand() % (right - left + 1);
swap(arr_idx[pivot_idx], arr_idx[right]);
int pivot_val = arr_idx[right].first;
int i = left;
for (int j = left; j if (arr_idx[j].first swap(arr_idx[i], arr_idx[j]);
++i;
}
}
swap(arr_idx[i], arr_idx[right]);
if (i == target_idx) return arr_idx[i].second;
else if (i > target_idx) right = i - 1;
else left = i + 1;
}
return arr_idx[left].second;
}
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
