这是众所周知的选择算法。参见http://en.wikipedia.org/wiki/Selection_algorithm。

我需要它来找到一组3x3x3体素值的中值。由于体积由十亿个体素组成，并且算法是递归的，因此最好快一点。通常，可以预期值相对接近。

到目前为止，我尝试过的最快已知算法使用快速排序分区功能。我想知道是否有更快的。

我使用两个堆“发明”了一个快20％的对象，但是我希望使用哈希可以使它甚至更快。在执行此操作之前，我想知道是否已经存在快速的快速解决方案。

我使用浮点数的事实无关紧要，因为在将符号位取反之后，它们可以被视为无符号整数。订单将被保留。

编辑：基准和源代码移到了由戴维·兰德曼（Davy Landman）建议的单独答案中。请参阅下面的chmike答案。

编辑
：Boojum在下面引用了到目前为止最有效的算法，作为到快速中值和双边过滤文件的链接，该文件现在是此问题的答案。这种方法的第一个聪明的主意是使用基数排序，第二个是结合共享大量像素的相邻像素的中值搜索。