标准排序网络，用于n的小值
我正在寻找一个5元素排序的排序网络实现，但由于我在SO上找不到好的参考，我想要求为所有小的n值排序网络，至少n = 3通过n = 6但更高的值也会很大。 一个好的答案至少应该将它们列为“交换”（在2个元素上排序）操作的序列，但是在低阶排序网络方面看到递归分解也可能会很好。
对于我的应用程序，我实际上只关心5个元素的中位数，而不是实际按顺序排列。 也就是说，只要中位数在正确的位置结束，结果中可能未指定其他4个元素的顺序。 可以使用与排序网络相关的方法来计算交换数量少于执行完整排序的中位数吗？ 如果是这样，我的问题（对于n = 5）和其他情况的这种解决方案也会得到一个很好的答案。
（注意：我已经标记了这个问题C，因为C是我使用的语言，我怀疑跟随C标签的人有很好的答案，但我真的不在乎答案实际上是用C语言编写而不是伪代码只要符合上述标准，它就可以很容易地转换为C语言。）
从每个部分中选择一个，大概是在你的硬件上以最快的速度运行，因为我们坚定地处于“恶魔般的优化”领域： http ： //smarterrecall.com/networks.html ，转载如下：
我创建了这个站点，列出了所有可能的最佳排序网络，最多可以使用matlab中的程序编写6个输入。 最长的运行时间是45秒的5输入。 如果您有兴趣与我联系，我可以通过rpl1 [AT] rice [DOT] edu Cheers，Richard L.
---------- - 2-input: 1 network [[1 2]] ---------- - 3-input: 6 networks [[1 2][1 3][2 3]] [[1 2][2 3][1 2]] [[1 3][1 2][2 3]] [[1 3][2 3][1 2]] [[2 3][1 2][2 3]] [[2 3][1 3][1 2]] ---------- - 4-input: 3 networks [[1 2][3 4][1 3][2 4][2 3]] [[1 3][2 4][1 2][3 4][2 3]] [[1 4][2 3][1 2][3 4][2 3]] ---------- - 5-input: 180 networks [[1 2][3 4][1 3][2 5][1 2][3 4][2 3][4 5][3 4]] [[1 2][3 4][1 3][2 5][2 3][4 5][1 2][3 4][2 3]] [[1 2][3 4][1 3][4 5][1 4][2 3][2 4][3 5][3 4]] [[1 2][3 4][1 3][4 5][2 5][3 4][1 3][2 4][2 3]] [[1 2][3 4][1 4][2 5][2 3][4 5][1 2][3 4][2 3]] [[1 2][3 4][1 4][3 5][1 3][2 5][2 3][4 5][3 4]] [[1 2][3 4][1 5][2 3][1 2][4 5][2 4][3 5][3 4]] [[1 2][3 4][1 5][2 4][1 3][2 5][2 3][4 5][3 4]] [[1 2][3 4][1 5][2 4][2 3][4 5][1 2][3 4][2 3]] [[1 2][3 4][2 3][4 5][1 4][3 5][1 2][3 4][2 3]] [[1 2][3 4][2 4][3 5][1 2][4 5][1 3][2 4][2 3]] [[1 2][3 4][2 4][3 5][1 3][2 5][2 3][4 5][3 4]] [[1 2][3 5][1 3][2 4][1 2][3 5][2 3][4 5][3 4]] [[1 2][3 5][1 3][2 4][2 3][4 5][1 2][3 4][2 3]] [[1 2][3 5][1 3][4 5][1 4][2 3][2 4][3 5][3 4]] [[1 2][3 5][1 3][4 5][2 5][3 4][1 3][2 4][2 3]] [[1 2][3 5][1 4][2 3][1 2][4 5][2 4][3 5][3 4]] [[1 2][3 5][1 4][2 5][1 3][2 4][2 3][4 5][3 4]] [[1 2][3 5][1 4][2 5][2 3][4 5][1 2][3 4][2 3]] [[1 2][3 5][1 5][2 4][2 3][4 5][1 2][3 4][2 3]] [[1 2][3 5][1 5][3 4][1 3][2 4][2 3][4 5][3 4]] [[1 2][3 5][2 3][4 5][1 4][3 5][1 2][3 4][2 3]] [[1 2][3 5][2 5][3 4][1 2][4 5][1 3][2 4][2 3]] [[1 2][3 5][2 5][3 4][1 3][2 4][2 3][4 5][3 4]] [[1 2][4 5][1 3][2 4][1 2][3 5][2 3][4 5][3 4]] [[1 2][4 5][1 3][2 5][1 4][2 3][2 4][3 5][3 4]] [[1 2][4 5][1 3][2 5][2 4][3 5][1 2][3 4][2 3]] [[1 2][4 5][1 4][2 3][1 2][4 5][2 4][3 5][3 4]] [[1 2][4 5][1 4][2 3][2 4][3 5][1 2][3 4][2 3]] [[1 2][4 5][1 4][3 5][1 3][2 4][2 3][4 5][3 4]] [[1 2][4 5][1 4][3 5][2 5][3 4][1 3][2 4][2 3]] [[1 2][4 5][1 5][2 3][2 4][3 5][1 2][3 4][2 3]] [[1 2][4 5][1 5][3 4][1 3][2 4][2 3][4 5][3 4]] [[1 2][4 5][2 4][3 5][1 3][4 5][1 2][3 4][2 3]] [[1 2][4 5][2 5][3 4][1 2][4 5][1 3][2 4][2 3]] [[1 2][4 5][2 5][3 4][1 3][2 4][2 3][4 5][3 4]] [[1 3][2 4][1 2][3 5][1 3][2 4][2 3][4 5][3 4]] [[1 3][2 4][1 2][3 5][2 3][4 5][1 2][3 4][2 3]] [[1 3][2 4][1 2][4 5][1 4][2 3][2 4][3 5][3 4]] [[1 3][2 4][1 2][4 5][2 4][3 5][1 2][3 4][2 3]] [[1 3][2 4][1 4][2 5][1 2][3 5][2 3][4 5][3 4]] [[1 3][2 4][1 4][3 5][2 3][4 5][1 2][3 4][2 3]] [[1 3][2 4][1 5][2 3][1 2][4 5][2 4][3 5][3 4]] [[1 3][2 4][1 5][3 4][1 2][3 5][2 3][4 5][3 4]] [[1 3][2 4][1 5][3 4][2 3][4 5][1 2][3 4][2 3]] [[1 3][2 4][2 3][4 5][1 4][3 5][1 2][3 4][2 3]] [[1 3][2 4][2 5][3 4][1 2][3 5][2 3][4 5][3 4]] [[1 3][2 4][2 5][3 4][1 3][4 5][1 2][3 4][2 3]] [[1 3][2 5][1 2][3 4][1 3][2 5][2 3][4 5][3 4]] [[1 3][2 5][1 2][3 4][2 3][4 5][1 2][3 4][2 3]] [[1 3][2 5][1 2][4 5][1 4][2 3][2 4][3 5][3 4]] [[1 3][2 5][1 2][4 5][2 4][3 5][1 2][3 4][2 3]] [[1 3][2 5][1 4][2 3][1 2][4 5][2 4][3 5][3 4]] [[1 3][2 5][1 4][3 5][1 2][3 4][2 3][4 5][3 4]] [[1 3][2 5][1 4][3 5][2 3][4 5][1 2][3 4][2 3]] [[1 3][2 5][1 5][2 4][1 2][3 4][2 3][4 5][3 4]] [[1 3][2 5][1 5][3 4][2 3][4 5][1 2][3 4][2 3]] [[1 3][2 5][2 3][4 5][1 4][3 5][1 2][3 4][2 3]] [[1 3][2 5][2 4][3 5][1 2][3 4][2 3][4 5][3 4]] [[1 3][2 5][2 4][3 5][1 3][4 5][1 2][3 4][2 3]] [[1 3][4 5][1 2][3 4][1 3][2 5][2 3][4 5][3 4]] [[1 3][4 5][1 2][3 5][1 4][2 3][2 4][3 5][3 4]] [[1 3][4 5][1 2][3 5][2 5][3 4][1 3][2 4][2 3]] [[1 3][4 5][1 4][2 3][1 2][4 5][2 4][3 5][3 4]] [[1 3][4 5][1 4][2 3][2 4][3 5][1 2][3 4][2 3]] [[1 3][4 5][1 4][2 5][1 2][3 4][2 3][4 5][3 4]] [[1 3][4 5][1 4][2 5][2 4][3 5][1 2][3 4][2 3]] [[1 3][4 5][1 5][2 3][2 4][3 5][1 2][3 4][2 3]] [[1 3][4 5][1 5][2 4][1 2][3 4][2 3][4 5][3 4]] [[1 3][4 5][2 4][3 5][1 2][3 4][2 3][4 5][3 4]] [[1 3][4 5][2 4][3 5][1 3][4 5][1 2][3 4][2 3]] [[1 3][4 5][2 5][3 4][1 2][4 5][1 3][2 4][2 3]] [[1 4][2 3][1 2][3 5][1 3][2 4][2 3][4 5][3 4]] [[1 4][2 3][1 2][3 5][2 3][4 5][1 2][3 4][2 3]] [[1 4][2 3][1 2][4 5][1 4][2 3][2 4][3 5][3 4]] [[1 4][2 3][1 2][4 5][2 4][3 5][1 2][3 4][2 3]] [[1 4][2 3][1 3][2 5][1 2][4 5][2 4][3 5][3 4]] [[1 4][2 3][1 3][4 5][2 4][3 5][1 2][3 4][2 3]] [[1 4][2 3][1 5][2 4][1 2][3 5][2 3][4 5][3 4]] [[1 4][2 3][1 5][3 4][1 2][3 5][2 3][4 5][3 4]] [[1 4][2 3][1 5][3 4][2 3][4 5][1 2][3 4][2 3]] [[1 4][2 3][2 4][3 5][1 3][4 5][1 2][3 4][2 3]] [[1 4][2 3][2 5][3 4][1 2][3 5][2 3][4 5][3 4]] [[1 4][2 3][2 5][3 4][1 3][4 5][1 2][3 4][2 3]] [[1 4][2 5][1 2][3 4][1 3][2 5][2 3][4 5][3 4]] [[1 4][2 5][1 2][3 4][2 3][4 5][1 2][3 4][2 3]] [[1 4][2 5][1 2][3 5][1 3][2 4][2 3][4 5][3 4]] [[1 4][2 5][1 2][3 5][2 3][4 5][1 2][3 4][2 3]] [[1 4][2 5][1 3][2 4][1 2][3 5][2 3][4 5][3 4]] [[1 4][2 5][1 3][4 5][1 2][3 4][2 3][4 5][3 4]] [[1 4][2 5][1 3][4 5][2 4][3 5][1 2][3 4][2 3]] [[1 4][2 5][1 5][2 3][1 2][3 4][2 3][4 5][3 4]] [[1 4][2 5][1 5][3 4][2 3][4 5][1 2][3 4][2 3]] [[1 4][2 5][2 3][4 5][1 2][3 4][2 3][4 5][3 4]] [[1 4][2 5][2 3][4 5][1 4][3 5][1 2][3 4][2 3]] [[1 4][2 5][2 4][3 5][1 3][4 5][1 2][3 4][2 3]] [[1 4][3 5][1 2][3 4][1 3][2 5][2 3][4 5][3 4]] [[1 4][3 5][1 2][4 5][1 3][2 4][2 3][4 5][3 4]] [[1 4][3 5][1 2][4 5][2 5][3 4][1 3][2 4][2 3]] [[1 4][3 5][1 3][2 4][1 2][3 5][2 3][4 5][3 4]] [[1 4][3 5][1 3][2 4][2 3][4 5][1 2][3 4][2 3]] [[1 4][3 5][1 3][2 5][1 2][3 4][2 3][4 5][3 4]] [[1 4][3 5][1 3][2 5][2 3][4 5][1 2][3 4][2 3]] [[1 4][3 5][1 5][2 3][1 2][3 4][2 3][4 5][3 4]] [[1 4][3 5][1 5][2 4][2 3][4 5][1 2][3 4][2 3]] [[1 4][3 5][2 3][4 5][1 2][3 4][2 3][4 5][3 4]] [[1 4][3 5][2 3][4 5][1 4][3 5][1 2][3 4][2 3]] [[1 4][3 5][2 5][3 4][1 2][4 5][1 3][2 4][2 3]] [[1 5][2 3][1 2][3 4][1 3][2 5][2 3][4 5][3 4]] [[1 5][2 3][1 2][3 4][2 3][4 5][1 2][3 4][2 3]] [[1 5][2 3][1 2][4 5][1 4][2 3][2 4][3 5][3 4]] [[1 5][2 3][1 2][4 5][2 4][3 5][1 2][3 4][2 3]] [[1 5][2 3][1 3][2 4][1 2][4 5][2 4][3 5][3 4]] [[1 5][2 3][1 3][4 5][2 4][3 5][1 2][3 4][2 3]] [[1 5][2 3][1 4][2 5][1 2][3 4][2 3][4 5][3 4]] [[1 5][2 3][1 4][3 5][1 2][3 4][2 3][4 5][3 4]] [[1 5][2 3][1 4][3 5][2 3][4 5][1 2][3 4][2 3]] [[1 5][2 3][2 4][3 5][1 2][3 4][2 3][4 5][3 4]] [[1 5][2 3][2 4][3 5][1 3][4 5][1 2][3 4][2 3]] [[1 5][2 3][2 5][3 4][1 3][4 5][1 2][3 4][2 3]] [[1 5][2 4][1 2][3 4][1 3][2 5][2 3][4 5][3 4]] [[1 5][2 4][1 2][3 4][2 3][4 5][1 2][3 4][2 3]] [[1 5][2 4][1 2][3 5][1 3][2 4][2 3][4 5][3 4]] [[1 5][2 4][1 2][3 5][2 3][4 5][1 2][3 4][2 3]] [[1 5][2 4][1 3][2 5][1 2][3 4][2 3][4 5][3 4]] [[1 5][2 4][1 3][4 5][1 2][3 4][2 3][4 5][3 4]] [[1 5][2 4][1 3][4 5][2 4][3 5][1 2][3 4][2 3]] [[1 5][2 4][1 4][2 3][1 2][3 5][2 3][4 5][3 4]] [[1 5][2 4][1 4][3 5][2 3][4 5][1 2][3 4][2 3]] [[1 5][2 4][2 3][4 5][1 2][3 4][2 3][4 5][3 4]] [[1 5][2 4][2 3][4 5][1 4][3 5][1 2][3 4][2 3]] [[1 5][2 4][2 5][3 4][1 3][4 5][1 2][3 4][2 3]] [[1 5][3 4][1 2][3 5][1 3][2 4][2 3][4 5][3 4]] [[1 5][3 4][1 2][4 5][1 3][2 4][2 3][4 5][3 4]] [[1 5][3 4][1 2][4 5][2 5][3 4][1 3][2 4][2 3]] [[1 5][3 4][1 3][2 4][1 2][3 5][2 3][4 5][3 4]] [[1 5][3 4][1 3][2 4][2 3][4 5][1 2][3 4][2 3]] [[1 5][3 4][1 3][2 5][1 2][3 4][2 3][4 5][3 4]] [[1 5][3 4][1 3][2 5][2 3][4 5][1 2][3 4][2 3]] [[1 5][3 4][1 4][2 3][1 2][3 5][2 3][4 5][3 4]] [[1 5][3 4][1 4][2 5][2 3][4 5][1 2][3 4][2 3]] [[1 5][3 4][2 3][4 5][1 2][3 4][2 3][4 5][3 4]] [[1 5][3 4][2 3][4 5][1 4][3 5][1 2][3 4][2 3]] [[1 5][3 4][2 4][3 5][1 2][4 5][1 3][2 4][2 3]] [[2 3][4 5][1 2][3 4][1 3][2 5][2 3][4 5][3 4]] [[2 3][4 5][1 2][3 5][1 4][2 3][2 4][3 5][3 4]] [[2 3][4 5][1 2][3 5][2 5][3 4][1 3][2 4][2 3]] [[2 3][4 5][1 3][2 4][1 2][4 5][2 4][3 5][3 4]] [[2 3][4 5][1 3][2 4][1 4][3 5][1 2][3 4][2 3]] [[2 3][4 5][1 3][2 5][1 4][3 5][1 2][3 4][2 3]] [[2 3][4 5][1 4][2 5][1 2][3 4][2 3][4 5][3 4]] [[2 3][4 5][1 4][3 5][1 2][3 4][2 3][4 5][3 4]] [[2 3][4 5][1 4][3 5][2 3][4 5][1 2][3 4][2 3]] [[2 3][4 5][1 5][2 4][1 2][3 4][2 3][4 5][3 4]] [[2 3][4 5][1 5][2 4][1 4][3 5][1 2][3 4][2 3]] [[2 3][4 5][1 5][3 4][1 2][4 5][1 3][2 4][2 3]] [[2 4][3 5][1 2][3 4][1 3][2 5][2 3][4 5][3 4]] [[2 4][3 5][1 2][4 5][1 3][2 4][2 3][4 5][3 4]] [[2 4][3 5][1 2][4 5][2 5][3 4][1 3][2 4][2 3]] [[2 4][3 5][1 3][2 5][1 2][3 4][2 3][4 5][3 4]] [[2 4][3 5][1 3][4 5][1 2][3 4][2 3][4 5][3 4]] [[2 4][3 5][1 3][4 5][2 4][3 5][1 2][3 4][2 3]] [[2 4][3 5][1 4][2 3][1 2][3 5][2 3][4 5][3 4]] [[2 4][3 5][1 4][2 3][1 3][4 5][1 2][3 4][2 3]] [[2 4][3 5][1 4][2 5][1 3][4 5][1 2][3 4][2 3]] [[2 4][3 5][1 5][2 3][1 2][3 4][2 3][4 5][3 4]] [[2 4][3 5][1 5][2 3][1 3][4 5][1 2][3 4][2 3]] [[2 4][3 5][1 5][3 4][1 2][4 5][1 3][2 4][2 3]] [[2 5][3 4][1 2][3 5][1 3][2 4][2 3][4 5][3 4]] [[2 5][3 4][1 2][4 5][1 3][2 4][2 3][4 5][3 4]] [[2 5][3 4][1 2][4 5][2 5][3 4][1 3][2 4][2 3]] [[2 5][3 4][1 3][2 4][1 2][3 5][2 3][4 5][3 4]] [[2 5][3 4][1 3][4 5][1 2][3 4][2 3][4 5][3 4]] [[2 5][3 4][1 3][4 5][2 4][3 5][1 2][3 4][2 3]] [[2 5][3 4][1 4][2 3][1 2][3 5][2 3][4 5][3 4]] [[2 5][3 4][1 4][2 3][1 3][4 5][1 2][3 4][2 3]] [[2 5][3 4][1 4][3 5][1 2][4 5][1 3][2 4][2 3]] [[2 5][3 4][1 5][2 3][1 2][3 4][2 3][4 5][3 4]] [[2 5][3 4][1 5][2 3][1 3][4 5][1 2][3 4][2 3]] [[2 5][3 4][1 5][2 4][1 3][4 5][1 2][3 4][2 3]] ---------- - 6-input: 90 networks [[1 2][3 4][5 6][1 3][2 5][4 6][1 2][3 4][5 6][2 3][4 5][3 4]] [[1 2][3 4][5 6][1 3][2 6][4 5][1 4][2 3][5 6][2 4][3 5][3 4]] [[1 2][3 4][5 6][1 4][2 6][3 5][1 3][2 5][4 6][2 3][4 5][3 4]] [[1 2][3 4][5 6][1 5][2 3][4 6][1 2][3 6][4 5][2 4][3 5][3 4]] [[1 2][3 4][5 6][1 5][2 4][3 6][1 3][2 5][4 6][2 3][4 5][3 4]] [[1 2][3 4][5 6][1 6][2 4][3 5][1 3][2 5][4 6][2 3][4 5][3 4]] [[1 2][3 5][4 6][1 3][2 4][5 6][1 2][3 5][4 6][2 3][4 5][3 4]] [[1 2][3 5][4 6][1 3][2 6][4 5][1 4][2 3][5 6][2 4][3 5][3 4]] [[1 2][3 5][4 6][1 4][2 3][5 6][1 2][3 6][4 5][2 4][3 5][3 4]] [[1 2][3 5][4 6][1 4][2 5][3 6][1 3][2 4][5 6][2 3][4 5][3 4]] [[1 2][3 5][4 6][1 5][2 6][3 4][1 3][2 4][5 6][2 3][4 5][3 4]] [[1 2][3 5][4 6][1 6][2 5][3 4][1 3][2 4][5 6][2 3][4 5][3 4]] [[1 2][3 6][4 5][1 3][2 4][5 6][1 2][3 5][4 6][2 3][4 5][3 4]] [[1 2][3 6][4 5][1 3][2 5][4 6][1 4][2 3][5 6][2 4][3 5][3 4]] [[1 2][3 6][4 5][1 4][2 3][5 6][1 2][3 6][4 5][2 4][3 5][3 4]] [[1 2][3 6][4 5][1 4][2 6][3 5][1 3][2 4][5 6][2 3][4 5][3 4]] [[1 2][3 6][4 5][1 5][2 6][3 4][1 3][2 4][5 6][2 3][4 5][3 4]] [[1 2][3 6][4 5][1 6][2 5][3 4][1 3][2 4][5 6][2 3][4 5][3 4]] [[1 3][2 4][5 6][1 2][3 5][4 6][1 3][2 4][5 6][2 3][4 5][3 4]] [[1 3][2 4][5 6][1 2][3 6][4 5][1 4][2 3][5 6][2 4][3 5][3 4]] [[1 3][2 4][5 6][1 4][2 5][3 6][1 2][3 5][4 6][2 3][4 5][3 4]] [[1 3][2 4][5 6][1 5][2 3][4 6][1 2][3 6][4 5][2 4][3 5][3 4]] [[1 3][2 4][5 6][1 5][2 6][3 4][1 2][3 5][4 6][2 3][4 5][3 4]] [[1 3][2 4][5 6][1 6][2 5][3 4][1 2][3 5][4 6][2 3][4 5][3 4]] [[1 3][2 5][4 6][1 2][3 4][5 6][1 3][2 5][4 6][2 3][4 5][3 4]] [[1 3][2 5][4 6][1 2][3 6][4 5][1 4][2 3][5 6][2 4][3 5][3 4]] [[1 3][2 5][4 6][1 4][2 3][5 6][1 2][3 6][4 5][2 4][3 5][3 4]] [[1 3][2 5][4 6][1 4][2 6][3 5][1 2][3 4][5 6][2 3][4 5][3 4]] [[1 3][2 5][4 6][1 5][2 4][3 6][1 2][3 4][5 6][2 3][4 5][3 4]] [[1 3][2 5][4 6][1 6][2 4][3 5][1 2][3 4][5 6][2 3][4 5][3 4]] [[1 3][2 6][4 5][1 2][3 4][5 6][1 3][2 5][4 6][2 3][4 5][3 4]] [[1 3][2 6][4 5][1 2][3 5][4 6][1 4][2 3][5 6][2 4][3 5][3 4]] [[1 3][2 6][4 5][1 4][2 3][5 6][1 2][3 6][4 5][2 4][3 5][3 4]] [[1 3][2 6][4 5][1 4][2 5][3 6][1 2][3 4][5 6][2 3][4 5][3 4]] [[1 3][2 6][4 5][1 5][2 4][3 6][1 2][3 4][5 6][2 3][4 5][3 4]] [[1 3][2 6][4 5][1 6][2 4][3 5][1 2][3 4][5 6][2 3][4 5][3 4]] [[1 4][2 3][5 6][1 2][3 5][4 6][1 3][2 4][5 6][2 3][4 5][3 4]] [[1 4][2 3][5 6][1 2][3 6][4 5][1 4][2 3][5 6][2 4][3 5][3 4]] [[1 4][2 3][5 6][1 3][2 5][4 6][1 2][3 6][4 5][2 4][3 5][3 4]] [[1 4][2 3][5 6][1 5][2 4][3 6][1 2][3 5][4 6][2 3][4 5][3 4]] [[1 4][2 3][5 6][1 5][2 6][3 4][1 2][3 5][4 6][2 3][4 5][3 4]] [[1 4][2 3][5 6][1 6][2 5][3 4][1 2][3 5][4 6][2 3][4 5][3 4]] [[1 4][2 5][3 6][1 2][3 4][5 6][1 3][2 5][4 6][2 3][4 5][3 4]] [[1 4][2 5][3 6][1 2][3 5][4 6][1 3][2 4][5 6][2 3][4 5][3 4]] [[1 4][2 5][3 6][1 3][2 4][5 6][1 2][3 5][4 6][2 3][4 5][3 4]] [[1 4][2 5][3 6][1 3][2 6][4 5][1 2][3 4][5 6][2 3][4 5][3 4]] [[1 4][2 5][3 6][1 5][2 3][4 6][1 2][3 4][5 6][2 3][4 5][3 4]] [[1 4][2 5][3 6][1 6][2 3][4 5][1 2][3 4][5 6][2 3][4 5][3 4]] [[1 4][2 6][3 5][1 2][3 4][5 6][1 3][2 5][4 6][2 3][4 5][3 4]] [[1 4][2 6][3 5][1 2][3 6][4 5][1 3][2 4][5 6][2 3][4 5][3 4]] [[1 4][2 6][3 5][1 3][2 4][5 6][1 2][3 5][4 6][2 3][4 5][3 4]] [[1 4][2 6][3 5][1 3][2 5][4 6][1 2][3 4][5 6][2 3][4 5][3 4]] [[1 4][2 6][3 5][1 5][2 3][4 6][1 2][3 4][5 6][2 3][4 5][3 4]] [[1 4][2 6][3 5][1 6][2 3][4 5][1 2][3 4][5 6][2 3][4 5][3 4]] [[1 5][2 3][4 6][1 2][3 4][5 6][1 3][2 5][4 6][2 3][4 5][3 4]] [[1 5][2 3][4 6][1 2][3 6][4 5][1 4][2 3][5 6][2 4][3 5][3 4]] [[1 5][2 3][4 6][1 3][2 4][5 6][1 2][3 6][4 5][2 4][3 5][3 4]] [[1 5][2 3][4 6][1 4][2 5][3 6][1 2][3 4][5 6][2 3][4 5][3 4]] [[1 5][2 3][4 6][1 4][2 6][3 5][1 2][3 4][5 6][2 3][4 5][3 4]] [[1 5][2 3][4 6][1 6][2 4][3 5][1 2][3 4][5 6][2 3][4 5][3 4]] [[1 5][2 4][3 6][1 2][3 4][5 6][1 3][2 5][4 6][2 3][4 5][3 4]] [[1 5][2 4][3 6][1 2][3 5][4 6][1 3][2 4][5 6][2 3][4 5][3 4]] [[1 5][2 4][3 6][1 3][2 5][4 6][1 2][3 4][5 6][2 3][4 5][3 4]] [[1 5][2 4][3 6][1 3][2 6][4 5][1 2][3 4][5 6][2 3][4 5][3 4]] [[1 5][2 4][3 6][1 4][2 3][5 6][1 2][3 5][4 6][2 3][4 5][3 4]] [[1 5][2 4][3 6][1 6][2 3][4 5][1 2][3 4][5 6][2 3][4 5][3 4]] [[1 5][2 6][3 4][1 2][3 5][4 6][1 3][2 4][5 6][2 3][4 5][3 4]] [[1 5][2 6][3 4][1 2][3 6][4 5][1 3][2 4][5 6][2 3][4 5][3 4]] [[1 5][2 6][3 4][1 3][2 4][5 6][1 2][3 5][4 6][2 3][4 5][3 4]] [[1 5][2 6][3 4][1 3][2 5][4 6][1 2][3 4][5 6][2 3][4 5][3 4]] [[1 5][2 6][3 4][1 4][2 3][5 6][1 2][3 5][4 6][2 3][4 5][3 4]] [[1 5][2 6][3 4][1 6][2 3][4 5][1 2][3 4][5 6][2 3][4 5][3 4]] [[1 6][2 3][4 5][1 2][3 4][5 6][1 3][2 5][4 6][2 3][4 5][3 4]] [[1 6][2 3][4 5][1 2][3 5][4 6][1 4][2 3][5 6][2 4][3 5][3 4]] [[1 6][2 3][4 5][1 3][2 4][5 6][1 2][3 6][4 5][2 4][3 5][3 4]] [[1 6][2 3][4 5][1 4][2 5][3 6][1 2][3 4][5 6][2 3][4 5][3 4]] [[1 6][2 3][4 5][1 4][2 6][3 5][1 2][3 4][5 6][2 3][4 5][3 4]] [[1 6][2 3][4 5][1 5][2 4][3 6][1 2][3 4][5 6][2 3][4 5][3 4]] [[1 6][2 4][3 5][1 2][3 4][5 6][1 3][2 5][4 6][2 3][4 5][3 4]] [[1 6][2 4][3 5][1 2][3 6][4 5][1 3][2 4][5 6][2 3][4 5][3 4]] [[1 6][2 4][3 5][1 3][2 5][4 6][1 2][3 4][5 6][2 3][4 5][3 4]] [[1 6][2 4][3 5][1 3][2 6][4 5][1 2][3 4][5 6][2 3][4 5][3 4]] [[1 6][2 4][3 5][1 4][2 3][5 6][1 2][3 5][4 6][2 3][4 5][3 4]] [[1 6][2 4][3 5][1 5][2 3][4 6][1 2][3 4][5 6][2 3][4 5][3 4]] [[1 6][2 5][3 4][1 2][3 5][4 6][1 3][2 4][5 6][2 3][4 5][3 4]] [[1 6][2 5][3 4][1 2][3 6][4 5][1 3][2 4][5 6][2 3][4 5][3 4]] [[1 6][2 5][3 4][1 3][2 4][5 6][1 2][3 5][4 6][2 3][4 5][3 4]] [[1 6][2 5][3 4][1 3][2 6][4 5][1 2][3 4][5 6][2 3][4 5][3 4]] [[1 6][2 5][3 4][1 4][2 3][5 6][1 2][3 5][4 6][2 3][4 5][3 4]] [[1 6][2 5][3 4][1 5][2 3][4 6][1 2][3 4][5 6][2 3][4 5][3 4]]
我个人在使用之前检查分拣网络是否正确，而不是在网上搜索一些随机页面。 蛮力“只”需要在有限的许多输入上运行它：“显然” n! 输入就足够了，实际上也是2**n （ https://en.wikipedia.org/wiki/Sorting_network#Zero-one_principle ）。
所有最优的5网络在最后一次交换中都涉及“3”，因此选择较少交换的中位数并不是那么容易。 不过，它可以在6次比较中完成。 如果您可以忽略对问题的抱怨，那么代码的方式将超出您的需求：
在C＃中计算“中位数为5”的代码
要选择中位数，您不一定要进行任何掉期，除非您想要保留所有5个值，否则可能只有一个无条件掉期。 此举可能就足够了。
提问者特别感兴趣的是基于排序网络的中位数为5的实现，所以我将解决这个具体情况。 对文献的简要回顾表明，根据各种指标，最佳解决方案是什么样的。
Michael Codish，LuísCruz-Filipe，Thorsten Ehlers，MikeMüller和Peter Schneider-Kamp。 “排序网络：到最后再回来。” 表1中的计算机与系统科学杂志 （2016）表明，对于n = 5，比较交换的最小数量是9，并且网络的最小深度是5.因为每个比较交换等于2分钟/最大操作，所需的最小/最大操作次数为18。
LukáŝSekanina，“中位电路的进化设计空间探索”。 在： EvoWorkshops ，2004年3月，第240-249页，给出了表1中10个最佳五输入中值选择网络所需的最小/最大操作次数。
William Gasarch，Wayne Kelly和William Pugh。 “找到小i的n中最大的n，n。” ACM SIGACT新闻 27，没有。 2（1996）：88-96，表1：中位数为5时至少需要进行6次比较。
通常，具有最少操作次数的分类网络不会简单地通过消除冗余操作而减少到具有最少操作次数的中值选择网络。 但是有可能找到对于至少某些n值以最佳方式减少的网络。 对于n = 5，对这种网络的powershell搜索是可行的。
下面的代码显示了五个输入分拣网络的四种变体，包括九个比较交换操作，或者18个最小/最大操作。 当使用FULL_SORT = 0编译时，这些变为具有10分钟/最大操作的中值选择网络。 因此，根据此指标，排序和中位数选择都是最佳选择。
但是，当用作分拣网络时，所有四种变体的深度为6而不是最小值为5。 此外，当基于比较而不是最小/最大操作配置为中值选择网络时，所有都需要七次而不是最少六次比较。
编译器资源管理器（godbolt）的编译结果示例：使用18分钟/最大值操作进行五输入排序 ，对五输入中值使用10分钟/最大值操作。
#include #include #include #define VARIANT 1 #define USE_MIN_MAX 1 #define FULL_SORT 0 typedef float T; #if USE_MIN_MAX #define MIN(a,b) ((T)(fmin(a,b))) #define MAX(a,b) ((T)(fmax(a,b))) #define SWAP(i,j) do { T s = MIN(a##i,a##j); T t = MAX(a##i,a##j); a##i = s; a##j = t; } while (0) #else // USE_MIN_MAX #define MIN(a,b) (((a) > (b)) ? (b) : (a)) #define MAX(a,b) (((a) > (b)) ? (a) : (b)) #define SWAP(i,j) do { if (a##i > a##j) { T temp = a##i; a##i = a##j; a##j = temp; }} while (0) #endif // USE_MIN_MAX /* Use sorting/median network to fully or partially sort array of five values and return the median value */ T network5 (T *a) { // copy to scalars T a0, a1, a2, a3, a4; a0=a[0];a1=a[1];a2=a[2];a3=a[3];a4=a[4]; #if VARIANT == 1 SWAP (0, 1); SWAP (2, 3); SWAP (0, 2); SWAP (1, 3); SWAP (2, 1); SWAP (1, 4); SWAP (1, 2); SWAP (0, 1); SWAP (3, 4); #elif VARIANT == 2 SWAP (3, 4); SWAP (0, 2); SWAP (2, 4); SWAP (0, 3); SWAP (2, 3); SWAP (1, 2); SWAP (0, 1); SWAP (2, 3); SWAP (3, 4); #elif VARIANT == 3 SWAP (3, 2); SWAP (0, 4); SWAP (2, 4); SWAP (0, 3); SWAP (2, 3); SWAP (1, 2); SWAP (0, 1); SWAP (2, 3); SWAP (3, 4); #elif VARIANT == 4 SWAP (2, 4); SWAP (0, 1); SWAP (0, 2); SWAP (1, 4); SWAP (2, 3); SWAP (1, 2); SWAP (2, 3); SWAP (0, 1); SWAP (3, 4); #else #error unsupported VARIANT #endif #if FULL_SORT // copy back sorted results a[0]=a0;a[1]=a1;a[2]=a2;a[3]=a3;a[4]=a4; #endif // return median-of-5 return a2; }
评论太久了。 Falken教授上面的答案可以在MATLAB中通过以下几行进行validation：使用一点find / replacement或regex-fu，写
sn{3} = [... [[1,2],[1,3],[2,3]];... [[1,2],[2,3],[1,2]];... [[1,3],[1,2],[2,3]];... [[1,3],[2,3],[1,2]];... [[2,3],[1,2],[2,3]];... [[2,3],[1,3],[1,2]]; ];
类似地，对于n的其他值，然后运行
for n = 3:6 test_in = cellfun(@str2num,num2cell(dec2bin(0:(2^n-1),n))); for j = 1:size(sn{n},1) test_out = test_in; for k = 1:2:size(sn{n},2) temp1 = test_out(:,sn{n}(j,k)); temp2 = test_out(:,sn{n}(j,k+1)); ind = temp2 < temp1; test_out(ind,sn{n}(j,k)) = temp2(ind); test_out(ind,sn{n}(j,k+1)) = temp1(ind); end end test = cellfun(@issorted,mat2cell(test_out,ones(1,2^n),n)); assert(all(test),['n = ',num2str(n),' failed test']); end
断言适用于n的每个值。