快速选择算法通过维护值与原始下标绑定的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
立即学习“C++免费学习笔记（深入）”；
这一步不可省略：若仅用值数组做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 <vector>
#include <random>
using namespace std;
int quickSelectIndex(vector<int>& nums, int k) {
int n = nums.size();
int target_idx = n - k; // 升序第target_idx小（0-based）
vector<pair<int, int>> arr_idx;
for (int i = 0; i < n; ++i)
arr_idx.emplace_back(nums[i], i);
int left = 0, right = n - 1;
while (left < right) {
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 < right; ++j) {
if (arr_idx[j].first <= pivot_val) {
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;
}
