std::nth_element不能直接交题，因其默认升序且仅重排使第n-k位就位，需手动换算下标；且oj常禁用stl或要求手写带随机化pivot的partition以考察原理，避免最坏o(n²)退化。
为什么 std::nth_element 不能直接拿去交题？
很多刷题人看到“平均 O(n) 查第 K 大”，第一反应是调 std::nth_element——它确实平均 O(n)，但默认按升序排列，且行为是“使第 n 个位置放好该有的元素”，不是“返回第 K 大”。你得手动算下标：nth_element(v.begin(), v.begin() + (n - k), v.end()) 才能得到第 K 大（假设数组无重复、k 从 1 开始）。更关键的是：LeetCode 或 OJ 常禁用 STL 算法，或要求手写 partition 过程来考察理解。
手写 partition 时 pivot 选错会导致最坏 O(n²)
快速选择的核心是每次 partition 后丢弃一半区间。但若 pivot 总选首/尾元素，面对已排序数组会退化成链表式递归。实际中建议：
- 随机选一个下标，swap 到右端作为 pivot（
swap(v[r], v[hi])） - 或者用「三数取中」：取
v[lo]、v[mid]、v[hi]的中位数，再 swap 到末尾 - 绝对不要写
pivot = v[lo]就直接 partition —— 测例里一堆单调数组等着卡你
quickSelect 的递归边界和 k 下标怎么对齐？
第 K 大 ≠ 第 K 小，也≠下标为 k 的元素。假设输入数组长度为 n，第 1 大是最大值，对应升序排列后的下标 n-1；第 K 大对应下标 n - k。所以入口要转一次：quickSelect(v, 0, n-1, n-k)。递归体里：
- partition 返回的是 pivot 最终落下的下标
pos - 若
pos == target，直接返回v[pos] - 若
pos > target，往左半段找：quickSelect(v, lo, pos-1, target) - 若
pos ，往右半段找：<code>quickSelect(v, pos+1, hi, target)
pos 而漏掉 pivot 自身。原地修改 vs 拷贝数组：空间和副作用怎么权衡？
算法本身可原地 partition，但如果你传入的是 const vector 或只读容器，就得先拷贝一份。拷贝代价是 O(n) 空间+时间，抵消不了算法优势。实操建议：
- 函数签名设为
int quickSelect(vector<int>& v, int k)</int>，明确允许修改输入 - 若业务逻辑不允许改原数组，加一层 wrapper：
auto tmp = v; return quickSelect(tmp, k); - 别在递归里反复 vector::begin()/end() 构造迭代器——指针或下标更轻量
- 小数组（比如 size
pivot 的交换逻辑、target 下标的换算、以及是否允许修改原数组——这三个点只要错一个，结果就全偏。调试时打印两轮 lo/hi/pos 就能立刻看出缩区间有没有越界或反向。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
