相关疑难解决方法(0)

这是我很久以前遇到的问题.我想我可能会问你的想法.假设我有一个非常小的数字列表(整数),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位处理器.

谢谢

常识认为，对于足够小的数组，插入排序是最好的。例如，Timsort对最多 64 个元素的数组使用（二进制）插入排序；来自维基百科：

一些分治算法（例如快速排序和合并排序）通过递归地将列表划分为较小的子列表然后进行排序来排序。在实践中，这些算法的一个有用的优化是使用插入排序对小子列表进行排序，因为插入排序优于这些更复杂的算法。插入排序具有优势的列表的大小因环境和实现而异，但通常在八到二十个元素之间。

这实际上是正确的吗？还有更好的选择吗？

如果这在很大程度上取决于平台，我对 .NET 最感兴趣。