求解数组第k小元素时QuickSelect与MaxHeap算法如何选型

两种算法没有绝对的优劣，优先选哪个完全取决于你的业务场景和约束条件，具体判断逻辑如下：

优先选择QuickSelect的场景 #

• 你的场景可以接受极偶然的最坏时间复杂度，或者可以使用**随机化选择基准值（pivot）**的优化版本：优化后的QuickSelect最坏O(n²)复杂度的触发概率无限趋近于0，普通业务场景下几乎不会遇到，实际运行效率远高于理论最坏情况。
• 你可以修改原数组，或者接受拷贝整个数组的成本：优化后的QuickSelect可以做到原地修改，空间复杂度仅为O(logn)（递归实现）或O(1)（迭代实现），不需要额外开辟大内存空间。
• 数据量较大，或者k值接近数组长度n：此时QuickSelect平均O(n)的时间复杂度优势会非常明显，远快于MaxHeap的O(n logk)（k接近n时logk约等于logn，整体复杂度退化为O(n logn)）。
  目前工业界主流的第k小/大元素实现（比如C++ STL中的nth_element）默认采用的就是优化版QuickSelect，就是因为其平均性能表现足够优秀。

优先选择MaxHeap的场景 #

• 你的场景对时间延迟有严格要求，完全不能接受偶发的超时：MaxHeap的时间复杂度稳定为O(n logk)，无论输入数据是什么样的分布，都不会出现性能抖动，适合实时计算、嵌入式等对稳定性要求极高的场景。
• 输入是流式数据，无法一次性拿到全量数据：MaxHeap不需要加载所有数据到内存，只需要维护大小为k的堆结构，数据随到随处理即可，而QuickSelect必须依赖全量数据才能完成选择。
• k值非常小：比如k=10以内，此时logk的数值极小，MaxHeap的运行速度和QuickSelect差距很小，但实现更简单，稳定性更高。
• 不允许修改原数组，也不愿意承担全量数组拷贝的成本：MaxHeap只需要开辟大小为k的额外空间，当n远大于k时，内存开销远低于全量拷贝数组后运行QuickSelect的成本。

内容的提问来源于stack exchange，提问作者Rishabh Kumar Singh