std::nth_element不是真正的TopK解法，因为它仅将第k小元素置于正确位置，不保证前k个元素有序或完整；若需升序返回最小k个数，必须额外调用std::sort对前k段排序，时间复杂度退化为O(n + k log k)。
为什么std::nth_element不是真正的TopK解法
它只保证第k个位置是正确值，左侧无序、右侧也无序，无法直接拿到最小的k个元素（除非额外排序或拷贝）。如果你要返回vector里最小的k个数且保持升序，std::nth_element必须配合std::sort对前k段再排——这就退化成O(n + k log k)，不是纯O(n)均摊。
真正满足「仅用O(n)均摊时间返回有序TopK」的，得自己实现带分区剪枝的快速选择变体：
- 每次
partition后只递归处理含第k小元素的那一侧 - 当目标区间长度 ≤ k 时，把整个区间加入结果，并提前终止
- 最终对收集到的所有候选数做一次小范围
std::sort（长度最多2k，均摊仍是O(n)）
手写quickselect_topk的关键三步
核心不是找第k小值，而是收集所有≤第k小值的元素。注意：存在重复值时，“第k小”可能有多个相等副本，必须全部包含。
实操建议：
- 使用三路划分（
lo,mid,hi），把等于pivot的全归到中间段，避免重复递归 - 递归前判断：
mid_start ≤ k-1 && k-1 ≤ mid_end→ 找到了，把[lo, mid_end]全加入结果 - 若
k-1 ，只递归左段；若k-1 > mid_end，递归右段并更新k为k - (mid_end - mid_start + 1) - 基准pivot用
std::uniform_int_distribution随机选，防最坏O(n²)退化
示例关键片段：
int pivot_idx = partition3way(arr, left, right);
int eq_start = ..., eq_end = ...;
if (k = eq_start) {
result.insert(result.end(), arr.begin() + left, arr.begin() + eq_end + 1);
return;
}
重复值多时partition3way比二路快一倍以上
二路划分在大量重复值下会把所有相等元素分到一侧，导致分区极度不均——比如数组全是5，每次只缩进1个位置，退化成O(n²)。
三路划分强制把等于pivot的挤在中间，递归深度稳定在O(log n)量级。实测在10⁶个重复元素+随机噪声混合数据上，二路平均耗时320ms，三路仅140ms。
注意点：
-
partition3way返回的是[eq_start, eq_end]闭区间，别漏掉eq_end - 移动指针时用
而非，避免越界；交换前检查i - STL里没有现成三路划分，
std::partition只支持二路，必须手写
边界与内存安全最容易错的三个地方
这类算法出core几乎都集中在索引计算和迭代器操作上：
- 传入
vector时，::iterator end()是开区间，right参数应设为arr.end() - 1，不是arr.end() - 递归调用时若用
vector切片（如vector(arr.begin()+l, arr.begin()+r+1)），会触发深拷贝，O(n)空间+时间爆炸——必须传原数组+左右下标 - 当
k == 0或k > arr.size()，需提前返回空结果或截断，否则partition里访问arr[k]越界
复杂点在于：均摊O(n)依赖于随机pivot和三路划分的协同，少一个就可能掉回O(n log n)甚至更差。实际工程中，如果k很小（比如k std::partial_sort反而更稳——它内部也是优化过的堆或插入排序，常数更低。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
