std::nth_element 不等于手写快选，因其不保证分区有序、不返回索引、内部优化导致行为差异（如重复值下提前终止），且 pivot 策略与步数统计不可控；手写时应选用 Hoare 分区、正确处理相等元素和边界，避免死循环。
为什么 std::nth_element 不等于“手写快选”
直接调用 std::nth_element 虽然能拿到第 K 大（或第 K 小）的值，但它不保证分区后左侧全 ≤ 右侧全 ≥，也不返回索引位置信息；更关键的是，它内部实现可能用中位数的中位数等优化策略，和教科书版快速选择在行为上不一致——比如对重复值多的数组，std::nth_element 可能提前终止而跳过部分比较，导致你无法复现“平均 O(n)”的步数统计逻辑。
实操建议：
- 调试或教学时，务必手写分区 + 递归/迭代版本，控制 pivot 选取方式（如随机、三数取中）
- 若需稳定性能，避免最坏 O(n²)，不要固定取
left或right为 pivot - 第 K 大 → 实际找的是升序排列后的第
n - k个下标（0-indexed），别在partition后直接比k
分区函数里 swap 的边界细节决定是否死循环
常见错误是 while 循环内两个指针越过彼此后仍交换，或没处理相等元素导致 pivot 卡在中间不动。标准 Lomuto 分区容易出这个问题，Hoare 分区更紧凑但初学者易写错边界条件。
推荐用 Hoare 风格并显式控制：
int partition(vector<int>& a, int left, int right) {
int pivot = a[left];
int i = left - 1, j = right + 1;
while (true) {
do i++; while (a[i] < pivot); // 注意：这里用 <，不是 <=
do j--; while (a[j] > pivot); // 同理，用 >
if (i >= j) return j;
swap(a[i], a[j]);
}
}
关键点：
立即学习“C++免费学习笔记（深入）”；
- 用
和 <code>>（而非/<code>>=）才能让相等元素自然分到两侧，避免某侧为空导致递归不收敛 -
return j，不是i：因为j是右段起点前一个位置，[left, j]是 ≤ pivot 区间 - 调用前确保
left ，否则直接返回（递归基）
递归转迭代时，栈里该压哪两个数
递归版每次只进一个分支，空间复杂度 O(log n)；手动迭代时若压入整个子区间，必须保证每次只处理一个子问题，否则会模拟成 DFS 全遍历，失去快选的剪枝意义。
正确做法是只保留待处理区间，且优先缩小右半边（或左半边，保持一致即可）：
int quickSelect(vector<int>& a, int left, int right, int k) {
while (left < right) {
int p = partition(a, left, right);
if (p == k) return a[k];
else if (k < p) right = p - 1;
else left = p + 1;
}
return a[left];
}
注意：
- 参数
k是目标下标（例如找第 3 大，数组长 10，则传k = 7），不是“第几个” - 循环体内不递归，只更新
left/right，所以不会爆栈，也无需额外栈空间 - 一旦
p == k立即返回，这是快选的核心剪枝点，别写成if (k 之类
平均 O(n) 的真实含义：期望比较次数 ≠ 每次都快
这个“平均”依赖于 pivot 的随机性。如果每次 pivot 恰好把数组二分，总比较次数是 n + n/2 + n/4 + … ≈ 2n；但如果连续几次都选到极值，就会退化成 n + (n−1) + (n−2) + … = O(n²)。实际中只要 pivot 均匀分布，数学期望就是 2n 左右。
验证技巧：
- 用
rand() % (right - left + 1)随机选 pivot，再与a[left]交换，比固定取首元素稳得多 - 测性能别只跑一次：对同一数组运行 100 次，看比较计数的标准差——若远大于均值，说明 pivot 策略有偏
- glibc 的
std::nth_element在小数组（
真正难的不是写对逻辑，而是让 pivot 选取既轻量又足够随机——生产环境别自己 roll，但理解它怎么崩，比记住公式重要。
