对非常小的列表进行排序的快速算法实现 [英] Fast algorithm implementation to sort very small list

问题描述

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

This is the problem I ran into long time ago. I thought I may ask your for your ideas. assume I have very small list of numbers (integers), 4 or 8 elements, that need to be sorted, fast. what would be the best approach/algorithm?

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

my approach was to use the max/min functions (10 functions to sort 4 numbers, no branches, 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)

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

I guess my question pertains more to implementation, rather than type of algorithm.

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

At this point it becomes somewhat hardware dependent , so let us assume Intel 64-bit processor with SSE3 .

谢谢

推荐答案

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

For small arrays like this, you should probably look into sorting networks. As you can see on that page, insertion sort can be expressed as a sorting network. However, if you know the size of the array beforehand, you can devise an optimal network. Take a look at this site that can help you to find optimal sorting networks for a given size of array (though optimal is only guaranteed up to a size of 16 I believe). The comparators are even grouped together in operations that can be done in parallel. The comparators are essentially the same as your s(x,y) function though if you really want this to be fast, you shouldn't be using min and max because then you're doing twice the number of comparisons that are necessary.

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

If you need this sorting algorithm to work on a wide range of sizes, then you should probably just go with insertion sort as others have suggested.

这篇关于对非常小的列表进行排序的快速算法实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！