文档介绍：排序网络华东师大二附中符文杰过去,我们学****了许多关于串行计算机的排序算法(如堆排序、快速排序), 这种类似的计算机每次只能执行一个操作。而今天,我所要介绍的排序算法是基于计算上的一种排序网络模型的基础之上的。在这种网络模型中可以同时执行多个比较操作。首先,我们要熟悉几个概念?排序网络是总能对其输入进行排序的比较网络。?一个比较网络仅由比较器和线路构成。?比较器是具有两个输入x和y以及两个输出x'和 y' 的一个装置且执行下列函数: x'=min(x,y) y'=max(x,y) 我们通常把比较器画为一竖垂直线,如图 1所示。输入在左面,输出在右面,较小的输入值在输出端的上部,较大的输入值在输出端的下部。因此,我们可以认为比较器对其两个输入进行了排序。我们假定每个比较操作占用的时间为 O(1) 。换句话说,我们假定自出现输入值 x和y到产生输出值 x'和 y'之间的时间为常数。?线路把一个值从一处传输到另一处。它可以把一个比较器的输出端与另一个比较器的输入端相连,在其他情况下它要么是网络的输入线,要么是网络的输出线。?比较网络就是一个由线路互相联接着的比较器的集合,我们把具有 n个输入的比较网络画成一个由 n条水平线组成的图,比较器则垂直地与两条水平线相连接。每个比较器的输入端要么与网络的 n 条输入线路 a 1,a 2,……,a n中的一条相连, 要么与另一个比较器的输出端相连接。类似地,每个比较器的输出端要么与网络的 n 条输出线路 b 1,b 2, ……,b n 中的 a 14211b 1 AC a 22432b 2E a 31123b 3 BD a 43344b 4图2 一条相连,要么与另一个比较器的输入端相连接。互相连接的比较器主要应满足如下要求:其互相连接所成的图中必须没有回路。只有当同时有两个输入时,比较器才能产生输出值。在每个比较器均运行单位时间的假设下,我们可以对比较网络的“运行时间”作出定义,这就是从输入线路接收到其值的时刻到所有输出线路收到其值所花费的时间。?排序网络是指对每个输入序列其输出序列均为单调递增(即 b 1?b 2?…?b n)的一种比较网络。当然并非每个比较网络都是排序网络,不过图 2 中的比较网络是排序网络。这个不难证明。比较网络和过程的相似之处在于它指定如何进行比较,其不同之处在于其实际规模决定于输入和输出的数目。因此,我们实际是在描述比较网络的家族。我们的目标就是寻找一个关于有效排序网络的家族排序程序 SORTER 。在家族 SORTER 中具有 n个输入和 n个输出的排序网络定义为 SORTER[ n]。在寻找这样的 SORTER 之前,我们首先应该明确如何去判断一个比较网络是否是排序网络。根据排序网络的定义,排序网络是对每个输入序列其输出序列均为单调递增的比较网络。根据这一点,如果我们要判断一个有 n 个输入和 n 个输出的比较网络是排序网络,就必须测试 n!种输入序列。这个工作量是非常大的,是否有简单一些的判断方法呢? 经过研究,我们发现了 0-1 原则。 0-1 原则认为: 如果对于属于集合{0, 1} 中的每个输入值(输入序列中的每个数是 0或 1) ,排序网络都能正确运行,则对任意的输入值,它也能正确运行。这样就把原来的问题变地简单一些了。下面让我们来证明 0-1 原则的正确性。我们先要证明一个引理