快速选择算法平均时间复杂度为O(n)，因其每次partition后仅递归处理含目标的一侧，期望规模减半，总操作量收敛于2n；而快排需递归两侧故为O(n log n)，退化情形（如pivot总选极值）下为O(n²)。
快速选择算法为什么平均时间复杂度是 O(n)
因为每次划分后，只递归处理包含目标位置的那一侧子数组，期望下一次处理的规模约为上一次的 1/2。数学上可推得总操作数收敛于 2n，即 O(n)；这和快排的 O(n log n) 本质区别在于：快排要两边都递归，而快速选择只进一边。
但要注意：这个“平均”依赖于 partition 的基准（pivot）足够随机。若每次选到最小或最大元素作 pivot（比如已排序数组中固定取首/尾），就会退化成 O(n²)。
实操建议：
- 务必对输入数组做随机打乱，或在
partition中用rand()随机选 pivot 索引，再与末尾交换 - 避免直接用
arr[0]或arr[r]作为 pivot —— 这是退化的常见源头 - 小规模子数组（如长度
如何返回第 K 大值的原始索引而非数值本身
快速选择默认返回值，但题目要求“所在位置”，意味着必须保留原始下标信息。不能只对值排序或 partition，得把索引和值绑定传递。
常见错误现象：nth_element 或手写 quickSelect 直接作用于值数组，结果找不到原位置。
正确做法是维护一个索引数组，并按对应值比较：
vector<int> idxs(arr.size());
iota(idxs.begin(), idxs.end(), 0);
nth_element(idxs.begin(), idxs.begin() + k - 1, idxs.end(),
[&arr](int i, int j) { return arr[i] > arr[j]; });
// 此时 idxs[k-1] 就是第 K 大值在原数组中的下标
</int>
注意：这里用 arr[i] > arr[j] 实现降序比较，对应“第 K 大”；若用升序，则应取 idxs[n - k]。
std::nth_element 能否直接用于找第 K 大位置
可以，但需注意两个关键点：比较器方向、迭代器偏移。
std::nth_element 保证第 n 个位置（从 0 开始）的元素就位，且左侧 ≤ 它、右侧 ≥ 它（默认升序）。要找第 K 大，等价于升序下的第 n - k 小元素。
实操建议：
- 调用形式为
nth_element(begin, begin + n - k, end)，不是begin + k - 1 - 若坚持用“第 K 大”语义，必须传自定义比较器
greater，此时目标位置是() begin + k - 1 - 它不保证其余元素有序，只保证分区性质 —— 所以不能靠它取 top-K 全部索引，除非多次调用或配合额外逻辑
示例（返回第 3 大值的原始下标）：
vector<int> arr = {3, 2, 1, 5, 6, 4};
vector<int> idxs = {0,1,2,3,4,5};
nth_element(idxs.begin(), idxs.begin() + 2, idxs.end(),
[&arr](int i, int j) { return arr[i] > arr[j]; });
// idxs[2] 即所求位置
</int></int>
手写 partition 时最容易踩的边界坑
手写 partition 是理解原理的关键，但 l 判断、swap 时机、循环后 pivot 归位这三处极易出错，导致死循环或结果错位。
典型错误现象：在某些输入下返回错误索引，或程序卡死在 while 循环里。
推荐使用 Lomuto 分区方案（更直观），并严格遵循以下顺序：
- 随机选 pivot 后与右端交换，统一处理
- 设
i = l - 1，遍历j从l到r - 1 - 仅当
arr[j] > pivot（求第 K 大）时才执行i++并swap(arr[i], arr[j]) - 最后
swap(arr[i+1], arr[r])，返回i + 1
特别注意：比较条件必须和目标一致 —— 求第 K 大，就要让大的元素往左堆；若写成 就会反向分区，后续递归区间也会全错。
复杂点其实在于：同一套 partition 逻辑，换一个比较方向或目标定义（K 小/K 大），整个索引映射关系就得重算。很多人调试半天才发现是这儿反了。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
