还有另一种用于基于 软堆
数据结构计算第k阶统计信息的算法，该算法是标准优先级队列的一种变体，允许“破坏”它存储的某些优先级。该算法在Wikipedia文章上有更详细的描述，但基本思想是使用软堆有效地（O（n）时间）为分区函数选择枢轴，以保证良好的拆分。从某种意义上讲，这只是中位数算法的修改版本，该算法使用（可以说）更直接的方法来选择枢轴元素。

软堆不是特别直观，但是在本文中对它们进行了很好的描述（“
Chazelle软堆的更简单实现和分析”），其中包括对数据结构的正式描述和分析。

但是，如果您想要一种真正快速，最坏情况的O（n）算法，请考虑研究 introselect
。该算法实际上非常出色。它通过使用quickselect算法开始，该算法巧妙地选择了一个枢轴，并使用它对数据进行分区。这在实践中非常快，但是在最坏情况下的行为却很糟糕。Introselect通过跟踪跟踪其进度的内部计数器来解决此问题。如果该算法看起来即将降级为O（n
2）时间，它会切换算法并使用中位数等值来确保最坏情况的保证。具体来说，它观察在每个步骤中丢弃了多少数组，并且如果在丢弃一半输入之前发生了一定数量的步骤，该算法将切换到中位数算法，以确保下一个支点是正确的然后使用quickselect重新启动。这保证了最坏情况下的O（n）时间。

该算法的优点是它在大多数输入上都非常快（因为quickselect非常快），但是在最坏情况下的行为也很大。可以
在本文中
找到此算法的说明以及相关的排序算法introsort （“自省排序和选择算法”）。

希望这可以帮助！