国家集训队2002论文集 符文杰

《国家集训队2002论文集 符文杰》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、排序网络-7-排序网络华东师大二附中符文杰过去，我们学习了许多关于串行计算机的排序算法（如堆排序、快速排序），这种类似的计算机每次只能执行一个操作。而今天，我所要介绍的排序算法是基于计算上的一种排序网络模型的基础之上的。在这种网络模型中可以同时执行多个比较操作。首先，我们要熟悉几个概念。l排序网络是总能对其输入进行排序的比较网络。l一个比较网络仅由比较器和线路构成。l比较器是具有两个输入x和y以及两个输出x'和y'的一个装置且执行下列函数：x'=min(x,y)y'=max(x,y)我们通常把比较器画为一竖垂直线，如图1所示。输入在左面，输出在右面，较小的输

2、入值在输出端的上部，较大的输入值在输出端的下部。因此，我们可以认为比较器对其两个输入进行了排序。我们假定每个比较操作占用的时间为O(1)。换句话说，我们假定自出现输入值x和y到产生输出值x'和y'之间的时间为常数。l线路把一个值从一处传输到另一处。它可以把一个比较器的输出端与另一个比较器的输入端相连，在其他情况下它要么是网络的输入线，要么是网络的输出线。a14211b1ACa22432b2Ea31123b3BDa43344b4图2l比较网络就是一个由线路互相联接着的比较器的集合，我们把具有n个输入的比较网络画成一个由n条水平线组成的图，比较器则垂直地与两条水

3、平线相连接。每个比较器的输入端要么与网络的n条输入线路a1,a2,……,an中的一条相连，要么与另一个比较器的输出端相连接。类似地，每个比较器的输出端要么与网络的n条输出线路b1,b2,……,bn排序网络-7-中的一条相连，要么与另一个比较器的输入端相连接。互相连接的比较器主要应满足如下要求：其互相连接所成的图中必须没有回路。只有当同时有两个输入时，比较器才能产生输出值。在每个比较器均运行单位时间的假设下，我们可以对比较网络的“运行时间”作出定义，这就是从输入线路接收到其值的时刻到所有输出线路收到其值所花费的时间。l排序网络是指对每个输入序列其输出序列均为单

4、调递增（即b1£b2£…£bn）的一种比较网络。当然并非每个比较网络都是排序网络，不过图2中的比较网络是排序网络。这个不难证明。比较网络和过程的相似之处在于它指定如何进行比较，其不同之处在于其实际规模决定于输入和输出的数目。因此，我们实际是在描述比较网络的家族。我们的目标就是寻找一个关于有效排序网络的家族排序程序SORTER。在家族SORTER中具有n个输入和n个输出的排序网络定义为SORTER[n]。在寻找这样的SORTER之前，我们首先应该明确如何去判断一个比较网络是否是排序网络。根据排序网络的定义，排序网络是对每个输入序列其输出序列均为单调递增的比较网

5、络。根据这一点，如果我们要判断一个有n个输入和n个输出的比较网络是排序网络，就必须测试n！种输入序列。这个工作量是非常大的，是否有简单一些的判断方法呢？经过研究，我们发现了0-1原则。0-1原则认为：如果对于属于集合{0，1}中的每个输入值（输入序列中的每个数是0或1），排序网络都能正确运行，则对任意的输入值，它也能正确运行。这样就把原来的问题变地简单一些了。下面让我们来证明0-1原则的正确性。我们先要证明一个引理。引理1：如果比较网络把输入序列a=转化为输出序列b=，则对任意单调递增函数f（不一定严格单调

6、递增），该网络把输入序列f(a)=转化为输出序列f(b)=。证明：我们可以采用数学归纳法来证。对比较网络中比较器的个数m进行归纳。¬证明m=1时引理1成立。（即只有一个比较器的情况）f(ai)min(f(ai),f(aj))=f(min(ai,aj))f(aj)max(f(ai),f(aj))=f(max(ai,aj))图3设这个比较器连接ai和aj。如果输入值为ai和aj，那么该比较器上端输出为min(ai,aj)，下端输出为max(ai,aj)。如果我们把f(ai)和

7、f(aj)作为该比较器的输入，由图3所示，则该比较器上端输出为min(f(ai),f(aj))，下端输出为max(f(ai),f(aj))。由于f排序网络-7-是单调递增函数，若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

8、=k时的情况。我们可以把具有k个比较器的比较网络拆成