std::nth_element是求第k大元素的最优解，平均O(n)时间复杂度；需将第k大转为第n−k小，调用nth_element(arr.begin(), arr.begin()+n−k, arr.end())，之后arr[n−k]即为结果。
用 std::nth_element 最快求第k大元素
绝大多数场景下，别手写快速选择——C++ 标准库的 std::nth_element 就是为此设计的，平均时间复杂度 O(n)，原地操作，且经过高度优化。它把第 k 小的元素放到位置 k 上（从 0 开始），其余元素不保证有序。
求“第k大”，只需转换为“第 n−k 小”：对大小为 n 的数组 arr，调用 std::nth_element(arr.begin(), arr.begin() + n - k, arr.end())，之后 arr[n - k] 就是答案。
- 注意：
k是从 1 开始计数的（即第 1 大、第 2 大……），所以索引要小心换算 - 如果数组是
vector，确保k满足1 ，否则行为未定义 - 该函数不保证其他元素有序，仅保证分区：左侧 ≤ 目标值，右侧 ≥ 目标值
手写快速选择时 pivot 选法很关键
自己实现快速选择（QuickSelect）时，最常踩的坑不是逻辑错，而是 pivot 选得差导致退化成 O(n²)。比如总选首/尾元素作 pivot，在已排序或逆序数组上会崩。
- 推荐用三数取中（median-of-three）：取首、中、尾三元素的中位数作为 pivot
- 更稳妥可用
std::random_device随机选下标，再 swap 到末尾参与划分 - 避免递归过深：对小规模子数组（如
size ）直接插入排序；对较大子问题，先处理较小段，再用尾递归优化处理较大段
注意 std::nth_element 的迭代器边界含义
它的签名是：std::nth_element(First, Nth, Last)，其中 [First, Last) 是左闭右开区间，Nth 必须在该区间内，且函数会把“第 std::distance(First, Nth) 小的元素”放到 Nth 位置。
立即学习“C++免费学习笔记（深入）”；
常见错误写法：nth_element(v.begin(), v.begin()+k, v.end()) 想求第k大，结果求的是第k小——没做 n−k−1 转换。
vectorarr = {3, 2, 1, 5, 6, 4}; int k = 2; // 求第2大 → 应该是第5小（索引4，因为size=6） int n = arr.size(); std::nth_element(arr.begin(), arr.begin() + n - k, arr.end()); cout << arr[n - k] << endl; // 输出 5
性能差异：比 std::sort 快，但不如堆（小k时）
当 k 很小（如前3大）或很大（如后3小），用 std::priority_queue 维护大小为 k 的堆反而更快，时间复杂度 O(n log k)，且空间可控；而 std::nth_element 总是扫描整个范围。
-
k == 1或k == n：直接用*max_element/*min_element，常数级优化 k 或k >= n − log n：考虑堆方案，避免无谓全扫描- 通用情况（k 在中间范围）、或需多次查询不同 k：预排序或建树（如平衡BST）可能更合适
快速选择的“快”是有条件的——它省去了完全排序的代价，但所有元素至少被访问一次，这点容易被忽略。
