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

Question

这是我很久以前遇到的问题。 我想我可以问问你的想法。 假设我有非常小的数字(整数)列表，4 或 8 个元素，需要快速排序。 什么是最好的方法/算法？

我的方法是使用最大/最小函数(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)

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

此时它变得有点依赖于硬件，所以让我们假设 Intel 64 位处理器和 SSE3。

谢谢

Answer 1

对于像这样的小数组，您可能应该查看 sorting networks .正如您在该页面上看到的那样，插入排序可以表示为排序网络。但是，如果您事先知道数组的大小，则可以设计出最佳网络。看看this site这可以帮助您找到给定大小的数组的最佳排序网络(尽管我认为最佳只能保证最大为 16)。比较器甚至在可以并行完成的操作中组合在一起。比较器本质上与您的 s(x,y) 函数相同，但如果您真的希望它更快，则不应使用 min 和 max，因为这样您就需要进行两倍的比较。

如果您需要这种排序算法适用于各种大小，那么您可能应该像其他人建议的那样使用插入排序。