这是众所周知的选择算法。参见http://en.wikipedia.org/wiki/Selection_algorithm。
我需要它来找到一组3x3x3体素值的中值。由于体积由十亿个体素组成，并且该算法是递归的，因此最好快一点。
通常，可以预期值相对接近。
到目前为止，我尝试过的最快已知算法使用快速排序分区功能。我想知道是否有更快的。
我使用两个堆“发明”了一个快20％的对象，但是我期望使用哈希可以使它甚至更快。在执行此操作之前，我想知道是否已经存在快速的快速解决方案。
我使用浮点数的事实无关紧要，因为在将符号位取反之后，它们可以被视为无符号整数。订单将被保留。
编辑:基准测试和源代码移入由建议的单独答案
戴维·兰德曼。请参阅下面的chmike答案。
编辑:Boojum在下面引用了迄今为止最有效的算法，作为到Fast Median and Bilateral Filtering论文的链接，该论文现在是该问题的答案。这种方法的第一个聪明的主意是使用基数排序，第二个是结合共享大量像素的相邻像素的中值搜索。
最佳答案
由于听起来好像您要对大量的体积数据执行中值滤波，因此您可能想看一下SIGGRAPH 2006的Fast Median and Bilateral Filtering论文。该论文涉及2D图像处理，但是您可能可以适应3D体积算法。如果没有别的，它可能会给您一些关于如何退后一步并从稍微不同的角度看问题的想法。