如何用平均O(n)时间复杂度实现快速选择算法查找数组中第K大的数？

本文共计1004个文字，预计阅读时间需要5分钟。

许多初学者看到C++标准库中的`std::nth_element，就以为能直接用来找出第K大的数——结果发现：

真正要落地，得自己实现带随机 pivot 的 Lomuto 或 Hoare 分区，否则退化到 O(n²) 是常态。

• std::nth_element 默认按 std::less 排，即升序；找第 K 大需传 std::greater<int>()</int> 或转换下标：第 K 大 = 第 n-K 小（0-indexed）
• 它内部虽用快速选择思想，但不可控 pivot 策略，无法满足算法题对“过程可复现”“最坏情况说明”的要求
• 若原数组只读、或需返回索引而非值，标准库接口就不够用了

如何正确实现随机 pivot 的分区函数？

核心是避免每次选首/尾元素导致有序输入时 O(n²)。必须在 [left, right] 内随机选一个下标，再把它 swap 到末尾，再执行一次标准 partition —— 这步漏掉，随机性就白做了。