可采用快速选择算法在O(n)平均时间内找到第K大数的原始索引，推荐索引绑定数组法：构建value-index结构体数组，分区时同步移动索引，最终返回elements[n-k].idx。
如果您需要在未排序的数组中查找第 K 大数值的原始索引位置（而非仅返回值），且要求平均时间复杂度为 O(n)，则可采用基于快速排序分区思想的快速选择算法。该算法不改变原数组顺序，通过维护原始索引映射关系实现定位。以下是三种不同实现方式：
一、索引绑定数组法（推荐）
将原数组元素与其初始下标打包为 pair 或结构体，在分区过程中同步移动索引，确保最终返回的是原始位置而非当前排序后的位置。此方法逻辑清晰，空间开销可控。
1、定义结构体 struct Element { int value; int idx; }; 创建大小为 n 的 Element 数组 elements，遍历原数组 arr 填充 elements[i] = {arr[i], i}；
2、实现分区函数 partition(elements, left, right)，以 elements[right].value 为 pivot，按 value 升序划分，并保证索引 idx 随 value 一同交换；
3、调用 quickSelect(elements, 0, n-1, n-k)，其中 n-k 是升序下第 (n−k) 小对应的位置（因第 K 大即升序第 n−k 小）；
4、算法终止时，elements[n-k].idx 即为所求原始索引位置；
5、注意：k 的取值范围必须满足 1 ≤ k ≤ n，且输入数组不能为空。
二、索引重映射辅助数组法
不修改原数组，也不复制元素值，而是维护一个独立的索引数组 idxs[0..n−1] = {0,1,…,n−1}，所有比较和交换仅作用于 idxs，访问 arr[idxs[i]] 获取对应值。分区操作只重排索引，从而保留原始位置信息。
1、声明 vector
2、编写分区函数 partition_idx(arr, idxs, left, right)，以 arr[idxs[right]] 为 pivot，仅交换 idxs 中的索引值；
3、执行 quickSelect_idx(arr, idxs, 0, n-1, n-k)；
4、递归结束时，idxs[n-k] 的值即为第 K 大数在原数组中的下标；
5、该方法避免了结构体拷贝开销，适合元素类型较大或不可拷贝的场景。
三、原地索引标记法（无额外容器）
利用原数组负号位或高位存储临时索引信息，仅适用于非负整数且数值范围允许的情况。通过位运算或符号翻转编码索引，实现零额外空间索引绑定。
1、确认 arr 中所有元素 ≥ 0 且最大值
2、首次遍历时，对每个 arr[i] 执行 arr[i] += (i
3、运行标准快速选择（基于 arr[i] & 0x3FFFFFFF 比较），分区过程保持高位索引不变；
4、找到目标位置 pos 后，提取原始索引：(arr[pos] >> 30) & 0x3；
5、此方案破坏原数组，结束后需恢复 arr[i] &= 0x3FFFFFFF；仅限竞赛环境或临时使用。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
