比较网络

比较网络由线路和比较器构成。一个比较器是一个具有两个输入 x 和 y 以及两个输出 x' 和 y' 的设备，其中

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

在比较网络中，输入出现在左侧，输出出现在右侧，最小的输入值出现在顶部输出，最大的输入值出现在底部输出。每个比较器在 O(1) 时间内运行。换句话说，我们认为输入值 x 和 y 出现到输出值 x' 和 y' 产生之间的时间是常数。

一条线路将值从一个地方传输到另一个地方。比较网络包含 n 个输入线路 a₁, a₂, ........a_n，要排序的输入值通过这些线路进入网络，还有 n 个输出线路 b₁, b₂, ......b_n，它们产生由网络计算的结果。

比较网络是一组由线路互连的比较器。比较器的运行时间可以定义为深度。

线路的深度： 比较网络的输入线路的深度为 0。现在，如果一个比较器有两个深度为 d_x 和 d_y' 的输入线路，那么它的输出线路的深度为 max (d_x, d_y) + 1。

排序网络是一种比较网络，对于每个输入序列，其输出序列单调递增（即 b₁≤ b₂ ≤ ....b_n）。

图：基于插入排序的排序网络