【算法导论】第二十七章 排序网络

一，比较网络

1）组成：线路和比较器

2）比较网络含义：就是一个由线路互相联接着的比较器的集合，我们把具有n个输入的比较网络画成一个由n条水平线组成的图，比较器则垂直地与两条水平线相连接。每个比较器的输入端要么与网络的n条输入线路a1,a2,……,an中的一条相连，要么与另一个比较器的输出端相连接。类似地，每个比较器的输出端要么与网络的n条输出线路b1,b2,……,bn中的一条相连，要么与另一个比较器的输入端相连接。互相连接的比较器主要应满足如下要求：其互相连接所成的图中必须没有回路。

只有当同时有两个输入时，比较器才能产生输出值。

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

3）比较网络示意图

4）排序网络：对每个输入序列其输出序列均为单调递增（即b_1<=b_2<=…<=b_n）的一种比较网络

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

6）双调序列：序列要么先单调递增然后再单调递减，要么先单调递减然后又单调递增。例如序列<1,4,6,8,3,2>和<9,8,3,2,4,6>都是双调的

二，双调排序网络

1）双调排序程序由log₂n个阶段组成，其中每一个阶段称为一个半清洁器。每个半清洁器是一个深度为1的比较网络，其中输入线I与输入线I+n/2进行比较，I=1,2,…,n/2（这里假设n为偶数）。图4即为一个具有8个输入和8个输出的半清洁器。

当由0和1组成的双调序列用作半清洁器的输入时，半清洁器产生的输出序列满足如下条件：

1>较小的值位于输出的上半部，较大的值位于输出的下半部。

2>两部分序列仍是双调的。

3>两部分序列中至少有一个是清洁的——全由0或1组成。（它的名称也是由此而来）

2）双调排序网络生成过程

通过递归地连接半清洁器，我们可以建立一个双调排序网络。双调排序网络[n]的第一阶段由半清洁器[n]组成，由定理1可知半清洁器[n]产生两个规模缩小一半的双调序列且满足上半部分的每个元素不比下半部分的任一个元素大。因此，我们可以运用两个双调排序网络[n/2]分别对两部分递归地进行排序，以此完成整个排序工作

我们只要把含n个元素的双调排序网络的第一个半清洁器修改一下就可以得到合并网络MERGER[n]。由于输入的上半部和下半部都是单调递增的，所以我们把比较网络的下半部分颠倒一下，输入就成了一个双调序列。添上半清洁器，再颠倒回去，半清洁器就变成了把输入a_i和a_n-i+1比较。这时，输出也被颠倒了。但是，一个双调序列颠倒了以后还是一个双调序列。