小编典典

快速算法实现,对非常小的列表进行排序

algorithm

这是我很久以前遇到的问题。我想我可能会问你的想法。假设我的数字(整数),4或8个元素的清单很小,需要快速排序。最佳方法/算法是什么?

我的方法是使用max / min函数(10个函数对4个数字进行排序,没有分支,iirc)。

// s(i,j) == max(i,j), min(i,j)
i,j = s(i,j)
k,l = s(k,l)
i,k = s(i,k) // i on top
j,l = s(j,l) // l on bottom
j,k = s(j,k)

我想我的问题更多地与实现有关,而不是算法类型。

此时,它在某种程度上取决于硬件,因此让我们假设带有SSE3的Intel 64位处理器。

谢谢


阅读 215

收藏
2020-07-28

共1个答案

小编典典

对于像这样的小型阵列,您可能应该研究排序网络。如您在该页面上所见,插入排序可以表示为排序网络。但是,如果您事先知道阵列的大小,则可以设计一个最佳网络。看一下该站点,它可以帮助您找到给定大小的阵列的最佳排序网络(尽管我相信只能保证最大大小为16)。比较器甚至以可以并行完成的操作组合在一起。比较器本质上与s(x,y)函数相同,但是如果您确实希望此比较快,则不应该使用min和max,因为这样做的结果是需要进行两次比较。

如果您需要这种排序算法来处理各种大小,那么您可能应该按照其他人的建议进行插入排序。

2020-07-28