快速选择算法能定位第K大值的下标，是因为它通过维护索引数组并基于原数组值比较划分，使每次partition后可映射目标秩到原始下标；关键在于操作索引而非值，配合三路划分处理重复值，迭代实现避免栈溢出。
快速选择算法为什么能定位第K大值的下标，而不是只返回值？
因为快速选择本质上是快排的剪枝版，每次划分后能确定某段数据在最终有序数组中的位置范围；只要记录每次划分的起始偏移量，就能把原始数组下标映射到目标位置。关键不是“找值”，而是“找这个值原来在哪儿”——所以必须传入原始索引数组或用结构体绑定值与下标。
常见错误是直接对 vector<int> 排序或拷贝值做 partition，结果返回的是排序后第K位的值，而非原数组中该值对应的下标。尤其当有重复值时，std::find 可能返回第一个匹配项，不一定是被选中的那个。
- 正确做法：维护一个索引数组
indices，所有比较和交换都作用于该数组，而比较依据是arr[indices[i]] - 第K大 → 对应升序中第
n-K小（0-indexed），即目标秩为target = n - K - partition 过程中，若基准元素落在
target位置，就立刻返回indices[target]
如何写一个不破坏原数组、支持重复值的 partition 函数？
标准 std::partition 不满足需求：它只按谓词分组，不返回基准位置，也无法控制三路划分。必须手写 Lomuto 或 Hoare 风格的 partition，并保证稳定性（不影响同值元素的相对顺序不是必须，但下标映射不能错）。
推荐用三路划分（Dutch National Flag）处理重复值，避免因大量相等元素导致退化。重点在于：比较操作始终通过原始数组取值，索引数组负责搬运下标。
立即学习“C++免费学习笔记（深入）”；
int partition(vector<int>& arr, vector<int>& indices, int left, int right) {
int pivot_idx = left + rand() % (right - left + 1);
swap(indices[pivot_idx], indices[right]);
int pivot = arr[indices[right]];
int lt = left, gt = right, i = left;
while (i <= gt) {
int val = arr[indices[i]];
if (val < pivot) {
swap(indices[lt++], indices[i++]);
} else if (val > pivot) {
swap(indices[i], indices[gt--]);
} else {
i++;
}
}
return lt; // lt 是第一个 ≥ pivot 的位置（升序语义）
}
递归 vs 迭代实现：为什么推荐迭代版？
递归写法简洁，但最坏情况下栈深度 O(n)，且 C++ 默认栈空间有限；而快速选择本意是避免完整排序，递归反而可能触发深度调用。迭代版本仅用 O(1) 额外空间，逻辑也更贴近“不断收缩搜索区间”的直觉。
- 迭代核心：用
while (left < right)控制范围，每次 partition 后根据lt和gt判断目标秩落在哪一段 - 若
target < lt，搜索左段：right = lt - 1 - 若
target > gt，搜索右段：left = gt + 1 - 否则
target落在等于 pivot 的区间内，直接返回任意一个对应下标（如indices[target]）
边界与性能陷阱：rand()、重复值、K越界怎么处理？
线上环境不加检查的快速选择极易 crash 或返回错误下标。三个高频坑：
-
K <= 0 || K > n：必须提前返回非法值（如 -1）或抛异常，C++ 中建议用assert(K > 0 && K <= n)或返回optional<int> - 没调用
srand(time(nullptr))或用std::random_device：导致每次选相同 pivot，面对有序数组直接退化成 O(n²) - 重复值多时，若只用两路划分，
lt和gt收缩慢，实际运行时间抖动大；三路划分虽代码略长，但实测在含 50% 重复值的数据上快 3× 以上
平均时间复杂度确实是 O(n)，但常数因子受 pivot 选取和划分质量影响很大；真实场景中，对小数组（如 n < 10）直接用 std::nth_element 更稳——它内部已做优化，且不强制要求你管理索引。
