algorithm - 蝴蝶网络排序

Question

我正在研究 C++ 中的 Robert Sedwick 算法中的奇数合并排序。

作为文本作者的一部分，作者提到了如何使用奇偶合并排序来实现排序网络中的并行排序。在这种情况下，作者提到了蝴蝶网络

我的问题是蝴蝶网络基本上是什么，为什么它被称为蝴蝶。用简单的例子进行解释将不胜感激。

我已经用谷歌搜索了它，但没有找到简单的示例解释。

Answer 1

蝴蝶网络是某种排序网络。分类网络可以被视为抽象网络（例如数据流网络）或非常具体的电路。

这些网络由输入和输出线以及一对比较器多路复用器组成，它们将输入值从一根线路由到另一根线。这是并行排序的一个例子。

资料来源：莱比锡大学

在上图中，输入在左侧，输出在右侧，方框是比较器。这个想法是，您可以在每个输入处放置从 0 到 15 的任意值，然后它们由比较器路由到输出（它检查输入值并决定路由到另一根导线或将其保持在同一根导线上），全部为 0值将被路由到顶部输出 (000)，所有 1 值将路由到第二个输出 (001) 等等。

恕我直言，这个名字来源于蝴蝶图，例如在快速傅里叶变换中，这种交叉的数据流类似于蝴蝶。

资料来源：维基百科

如果您查看蝴蝶网络的第一张图，您会看到它一遍又一遍地重复。