信息学奥赛算法合集之《排序网络》

排序网络 - 1 -

排序网络

过去，我们学习了许多关于串行计算机的排序算法（如堆排序、快速排序），这种类似的计算机每次只能执行一个操作。而今天，我所要介绍的排序算法是基于计算上的一种排序网络模型的基础之上的。在这种网络模型中可以同时执行多个比较操作。

首先，我们要熟悉几个概念

? 排序网络是总能对其输入进行排序的比较网络。

? 一个比较网络仅由比较器和线路构成。

? 比较器是具有两个输入x和y以及两个输出x'和y'的一个装置且执行下

列函数：

x'=min(x,y)

y'=max(x,y)

我们通常把比较器画为一竖垂直线，如图1所示。输入在左面，输出在右面，较小的输入值在输出端的上部，较大的输入值在输出端的下部。因此，我们可以认为比较器对其两个输入进行了排序。

我们假定每个比较操作占用的时间为O(1)。换句话说，我们假定自出现输入值x和y到产生输出值x'和y'之间的时间为常数。

? 线路把一个值从一处传输到另一处。它可以把一个比较器的输出端与另

一个比较器的输入端相连，在其他情况下它要么是网络的输入线，要么是网络的输出线。

? 比较网络就是一个由线路互相联接着的比较器的集合，我们把具有n个

输入的比较网络画成一个由n条水平线组成的图，比较器则垂直地与两条水平线相连接。每个比较器的输入端要么与网络的n条输入线路a1,a2,……,an中的一条相连，要么与另一个比较器的输出端相连接。类似地，每个比较器的输出端要么与网络的n条输出线路b1,b2,……,bn中的

a1 4 2 1 1 b1 A C a2 2 4 3 2 b2 E a3 1 1 2 3 b3 B D a4 3 3 4 4 b4

图 2

排序网络 - 2 -

一条相连，要么与另一个比较器的输入端相连接。互相连接的比较器主要应满足如下要求：其互相连接所成的图中必须没有回路。 只有当同时有两个输入时，比较器才能产生输出值。

在每个比较器均运行单位时间的假设下，我们可以对比较网络的“运行时间”作出定义，这就是从输入线路接收到其值的时刻到所有输出线路收到其值所花费的时间。

? 排序网络是指对每个输入序列其输出序列均为单调递增（即b1?b2?…

?bn）的一种比较网络。当然并非每个比较网络都是排序网络，不过图2中的比较网络是排序网络。这个不难证明。

比较网络和过程的相似之处在于它指定如何进行比较，其不同之处在于其实际规模决定于输入和输出的数目。因此，我们实际是在描述比较网络的家族。我们的目标就是寻找一个关于有效排序网络的家族排序程序SORTER。在家族SORTER中具有n个输入和n个输出的排序网络定义为SORTER[n]。

在寻找这样的SORTER之前，我们首先应该明确如何去判断一个比较网络是否是排序网络。根据排序网络的定义，排序网络是对每个输入序列其输出序列均为单调递增的比较网络。根据这一点，如果我们要判断一个有n个输入和n个输出的比较网络是排序网络，就必须测试n！种输入序列。这个工作量是非常大的，是否有简单一些的判断方法呢？

经过研究，我们发现了0-1原则。0-1原则认为：如果对于属于集合{0，1}中的每个输入值（输入序列中的每个数是0或1），排序网络都能正确运行，则对任意的输入值，它也能正确运行。这样就把原来的问题变地简单一些了。

下面让我们来证明0-1原则的正确性。我们先要证明一个引理。

引理1：如果比较网络把输入序列a=转化为输出序列b=<

b1,b2,……,bn >，则对任意单调递增函数f（不一定严格单调递增），该网络把输入序列f(a)=转化为输出序列f(b)=。

证明：我们可以采用数学归纳法来证。对比较网络中比较器的个数m进行归纳。

证明m=1时引理1成立。（即只有一个比较器的情况）

设这个比较器连接ai和aj。

如果输入值为ai和aj，那么该比较器上端输出为min(ai,aj)，下端输出为max(ai,aj)。如果我们把f(ai)和f(aj)作为该比较器的输入，由图3所示，则该比

f(ai) min(f (ai),f (aj) )=f (min(ai, aj) )

f(aj) max(f (ai),f (aj) )=f (max(ai, aj) )

图 3

排序网络 - 3 -

较器上端输出为min(f(ai),f(aj))，下端输出为max(f(ai),f(aj))。由于f是单调递增函数，若ai?aj，则f(ai)?f(aj)。因此我们有下列等式：

min(f(ai),f(aj))=f(min(ai,aj)) max(f(ai),f(aj))=f(max(ai,aj))

所以当我们把f(ai)和f(aj)作为比较器的输入时，它所得出的值就是f(min(ai,aj))和f(max(ai,aj))。所以在m=1时，引理1成立。

当比较器的个数m

不妨设输入序列a=经过比较器S1后，成为序列c=< c1,c2,……,cn>，再把它作为输入序列经过比较器S2后，成为最终的输出序列b=< b1,b2,……,bn >。

那么由归纳假设知：如果把f(a)=作为比较器S1的输入序列，输出即为f(c)=；再把f(c)=作为比较器S2的输入序列，得到最终的输出序列为f(b)=。

因此，引理1在m=k时亦成立。

综上所述，无论比较网络中有多少个比较器，引理1均成立。 证毕。

有了引理1作为基础，我们就可以证明0-1原则了。

0-1原则：如果一个具有n个输入的比较网络能够对所有可能存在的2n个0和1组成的序列进行正确的排序，则对所有任意数组成的序列，该比较网络也可能对其正确排序。

证明：我们用反证法来证明。假设这个比较网络能对所有0-1序列进行排序，但存在一个由任意数组成的序列，网络不能对该序列正确地排序。这就是说，存在一个输入序列，其中两个元素ai和aj满足ai

?0如果x?aif(x)???1如果x?ai因为当a=作为输入序列时，其输出序列中aj位于ai之前，所以由引理1可知当序列f(a)=作为输入序列时，其输出序列中f(aj)必位于f(ai)之前。但由于f(aj)=1，f(ai)=0。这样我们就推出网络不能正确地对0-1序列进行排序，与假设矛盾。

0-1原则得证。

当我们构造排序网络和其它比较网络时，0-1原则使得我们可以把注意力集