快速的algorithm实现sorting非常小的列表
这是我很久以前遇到的问题。 我想我可能会问你的想法。 假设我有非常小的数字（整数），4或8个元素，需要sorting，快速列表。 什么是最好的方法/algorithm？
我的方法是使用最大/最小function（10个函数来sorting4个数字，没有分支，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) 我想我的问题更多地涉及到实现，而不是types的algorithm。
在这一点上，它变得有点依赖于硬件，所以让我们假设带有SSE3的Intel 64位处理器。
谢谢
对于这样的小型数组，您应该考虑分类networking 。 正如您在该页面上看到的，插入sorting可以表示为sortingnetworking。 但是，如果事先知道arrays的大小，则可以devise出最佳的networking。 看看这个网站 ，可以帮助你find一个给定大小的arrays的最佳分类networking（虽然最好只能保证大小16我相信）。 比较者甚至可以在可以并行完成的操作中组合在一起。 比较器基本上和你的s（x，y）函数相同，但是如果你真的希望这个速度很快的话，你不应该使用min和max，因为这样你就可以做两次必要的比较。
如果你需要这种sortingalgorithm来处理大量的尺寸，那么你可能应该像其他人一样使用插入sorting。
我看到你已经有一个解决scheme，使用5个比较（假设s（i，j）比较这两个数字一次，或者交换或不交换）。 如果你坚持基于比较的sorting，那么你不能做任何less于5比较。
这可以被certificate，因为有4！ = 24种可能的方式来订购4个号码。 每个比较只能削减一半的可能性，所以通过4次比较，只能区分2 ^ 4 = 16个可能的sorting。
要sortingless量的数字，你需要一个简单的algorithm，因为复杂性会增加开销。
sorting例如四个项目的最有效方法是将sortingalgorithm解开为线性比较，从而消除所有的开销：
function sort(i,j,k,l) { if (i < j) { if (j < k) { if (k < l) return [i,j,k,l]; if (j < l) return [i,j,l,k]; if (i < l) return [i,l,j,k]; return [l,i,j,k]; } else if (i < k) { if (j < l) return [i,k,j,l]; if (k < l) return [i,k,l,j]; if (i < l) return [i,l,k,j]; return [l,i,k,j]; } else { if (j < l) return [k,i,j,l]; if (i < l) return [k,i,l,j]; if (k < l) return [k,l,i,j]; return [l,k,i,j]; } } else { if (i < k) { if (k < l) return [j,i,k,l]; if (i < l) return [j,i,l,k]; if (j < l) return [j,l,i,k]; return [l,j,i,k]; } else if (j < k) { if (i < l) return [j,k,i,l]; if (k < l) return [j,k,l,i]; if (j < l) return [j,l,k,i]; return [l,j,k,i]; } else { if (i < l) return [k,j,i,l]; if (j < l) return [k,j,l,i]; if (k < l) return [k,l,j,i]; return [l,k,j,i]; } } }
但是，对于每个添加的项目，代码都会增长很多。 添加第五个项目使代码大约四倍大。 在八个项目大约是30000行，所以虽然它仍然是最有效的，它是很多的代码，你将不得不写一个程序，编写代码，以使其正确。
插入sorting被认为是最好的小arrays。 查看小arrays的快速稳定sorting（32或64个元素）
sortingnetworking可以很容易地在SIMD中实现，尽pipe它在N = 16左右开始变得难看。对于N = 4或N = 8，虽然这将是一个不错的select。 理想情况下，您需要大量的小数据集来同时进行sorting，也就是说，如果要sorting8位值，那么您至less需要16个数据集进行sorting – 在 SIMD向量中执行这种操作要困难得多。
另请参见： 最快固定长度6 int数组
对于这样一个小的数据集，你想尽可能简单的algorithm。 更有可能的是，一个基本的插入sorting将尽你所能。
需要了解更多关于这个系统运行的信息，你需要做多less次这样的sorting等等，但是一般的规则是保持简单。 快速sorting等是不利的。
