Quick select规避O(n²)最坏场景：选随机pivot还是median of medians（MoM）？

随机选择pivot的适用场景 #

• 通用业务场景下的分位数、Top K计算：比如计算接口响应时间P99、用户行为分档、大列表筛选第k大元素这类日常需求，随机pivot几乎不产生额外性能开销，实际运行效率很高；算法退化到O(n²)的概率低到可忽略，完全不需要为这种极罕见的情况牺牲日常运行速度。
• 资源受限的轻量化部署场景：比如边缘端设备、嵌入式系统、低功耗IoT节点上的轻量数据处理，这类场景没法承担MoM方案带来的分组遍历、递归选pivot的额外计算和内存开销，随机选pivot只需要几行随机数生成逻辑，代码极简、占用资源极少。
• 通用标准库、基础工具的实现选择：绝大多数编程语言内置的nth_element、数组分区类工具接口，都优先用随机pivot方案，因为平均性能最优，不需要为了理论上的严格O(n)上界，拉低绝大多数常规输入下的运行速度。

Median of Medians（MoM）方法的适用场景 #

• 有严格性能确定性要求的实时系统场景：比如硬实时任务、对延迟有SLA硬约束的在线服务，哪怕百万分之一概率出现O(n²)的性能抖动，都可能触发超时、雪崩类故障，这类场景必须严格锁定最坏时间复杂度为O(n)，不能靠概率赌运行稳定。
• 面对对抗性构造输入的场景：比如算法竞赛解题、需要应对恶意构造测试用例的程序，这类场景下输入是刻意设计来卡算法性能的，随机pivot有可能被针对性命中退化路径，而MoM是确定性选pivot，完全不受输入结构影响，不会被卡到O(n²)。
• 超大规模离线批量计算场景：比如对TB级静态日志、全量用户数据计算整体分位数，这类任务如果中途碰到随机pivot的性能退化，原本几小时的计算可能被拉长到数天，用MoM可以把计算时间的上界锁死，方便做任务排期和资源容量规划，哪怕常数开销更高，也比计算过程中突发性能崩盘可控。

实际选型时的核心判断标准：优先用随机pivot方案，只有当场景对性能确定性有硬约束、或者可能碰到对抗性输入时，再选择MoM方案。毕竟MoM的pivot选择过程需要多次遍历数组，相同数据规模下运行速度通常比随机pivot实现慢2-3倍，额外开销很高。

内容的提问来源于stack exchange，提问作者user5965026