比较网络

比较网络这是一种能够始终对输入数据进行排序的排序网络。在比较网络中，比较器是一种具有两个输入（x, y）和两个输出（x’, y’）的装置。它的功能就是进行如下的比较操作：

x' = min(x, y),
y' = max(x, y) 

比较器通常被表示为一条垂直的直线，其中输入端位于直线的左侧，输出端则位于右侧。较小的输入值会被放在输出的上方，而较大的输入值则会被放在输出的下方。因此，可以将比较器看作是对两个输入值进行排序的过程。假设每个比较器的处理时间都是O(1)，也就是说，从输入值被传入到输出结果生成之间的时间都是恒定的。比较网络的第二个组成部分就是……电线它承担着将某个数值从一个地方传输到另一个地方的功能。 这些要么是网络输入线，要么是网络输出线。 这些导线能够将比较器的输入端与另一个设备的输出端连接起来。只有当比较器的两个输入端都有数据时，它才会产生输出信号。 现在，假设每个比较器都需要单位时间来完成其工作，那么“运行时间”就可以被定义了。 运行时间，指的是在输入线接收到数值之后，输出线接收到这些数值所需的时间。 其正式定义如下： 比较网络的输入线路的深度为0。 现在，如果d1和d2分别表示两条输入线的深度，那么输出线的深度则应为max(d1, d2) + 1。 比较器的深度，指的是其输出引脚的深度。属性：

• 图必须是无环的。
• 只有当输入资源可用时，才能产生输出。
• 如果输入数据可用，那么比较器会并行处理这些数据。
• 排序网络是一种比较型网络，其输出结果经过排序处理。
• 并非所有的比较网络都是排序网络。
• 比较网络实际上是一种机制，它规定了如何进行各种比较。

定理：

1. 如果一个具有n个输入的比较网络能够正确地对所有可能的由0和1构成的2n个序列进行排序，那么它当然也能正确地对任意数量的序列进行排序。
2. 如果有一个比较网络，它能够将输入值 a = ha1, a2, ……, ani 转换为输出值 b = hb1, b2, ……, bni。那么，对于任何单调递增的函数 f，该网络都能正确地进行转换。

   f(a) = hf(a1), f(a2), . . ., f(an)i 
   into 
   f(b) = hf(b1), f(b2), . . ., f(bn)i