快速,小面积和低延迟的部分排序算法

Question

我正在寻找一个快速的方式做81号的部分排序 - 理想的情况下我期待提取最低16个值(它不是必需的16是在绝对正确的顺序).

这样做的目标是在FPGA专用硬件 - 所以这个稍微复杂的问题,因为我想要的结果执行的面积尽可能小.我看了看,并实施了奇偶合并排序算法,但我的理想在寻找什么,可能是我的需求更有效的(贸易算法实现大小的部分排序,以便给予最低16,不一定而不是一个完整的)

任何建议都会非常受欢迎

非常感谢

Answer 1

这可以及时完成O(nlog_k),在你的情况下n = 81和k = 16.当你处理大量的元素时,这是非常有效的O(nlog_n).

算法如下:

1. Init最大堆数据结构.此堆将包含您的前16个.此堆的大小不会超过16,并且它具有用于插入和删除的log(k)
2. 迭代n个数字列表.每个n:
   • 如果堆少于16个元素,只需添加它
   • 如果heap有16个元素,则n与堆中的max 进行比较(如果它大于max则跳过,如果小于max,则删除max并添加n.)

这样,在每次迭代中,您都会跟踪当前处理的列表中最小的k个数字.

Answer 2

如果您正在寻找通用算法，那么您可以使用快速排序的一个版本。快速排序围绕枢轴元素对值进行排序。您选择一个基准并对数组进行排序。然后你会得到 x 值 < 枢轴和 (nx-1) 个较大的值。根据 x，您选择任一数组来继续处理。如果x>16，那么你就知道你要找的数字都在x数组中，你可以继续排序。如果不是，那么您知道 x 最低，现在可以递归地在另一个数组中查找 16-x 个其他值。

快速排序的结果数组并未完全排序，您只知道它们比您的主元小或大。维基百科和论文中的一些信息。