爱华网突然发现自己一个礼拜以上没有写日志了，并且上一篇纯属吐槽。不行，不能这么堕落！
今天在黑书上看见排序网络。恩。发现真是个好东西。不知道为什么自己特别喜欢像自动机啦，排序网络之类的这种可以实现“自动”干什么什么的，并且能够多次使用非一次性的东西。喵。
当第一次在CLRS上看到这张经典的排序网络的图的时候（黑白）：
我就看上了这个东西。很美有木有！
OK。不扯了。
参考的是http://wenku.baidu.com/view/1180bfc24028915f804dc2be.html
关于排序网络，有几个重要概念。
比较器(comparator)：
简单来说就是一个机器，输入两条线路，输出两条线路。输入x和y，比较之后min(x,y)从上面的输出线输出，max(x,y)从下面的输出线输出。暂且把一个这样的比较器叫做一个gate。
比较网络(comparisonnetwork)：
（这张图也很美有木有！）简单来说就是一堆平行的线代表各种线路，左边输入，经过中间有很多很多垂直于线路的线，它们就是gate，进行运算，最后右边是得到的输出序列。
排序网络(sortingnetwork):
很好理解，就是对于任意的输入序列，总是能够输出递增序列的网络就是排序网络。
有趣的是，本篇开头的那张美丽的倒三角就是一个排序网络！为什么呢？把它稍微画的不一样一点：
我们可以发现，这个东西gate的排列有些类似冒泡排序的感觉，事实上，当它在计算的时候，也有冒泡排序的感觉，不信的话可以自己随便搞个输入序列手模一下，总之算的时候会感觉很开心（“开心”，嗯，这个词很恰当）。
但是我们可以发现，这个排序网络gate的数量是n^2个，并需要2n-1个单位时间来完成排序。不是很靠谱啊。有木有更加靠谱的构造方法呢？答案是肯定的。
对了，还有一个重要概念，那就是0-1原则(TheZero-One Principle)：
一个比较网络是排序网络当且仅当它可以正确的把任意只由0和1组成的输入序列排成升序。
证明这里略了，论文里有详细讲述。
有了这个我们就可以把检测一个比较网络是否是排序网络的工作只放在对于所有0-1串来说了。
于是开始构造。
有一个叫做双调序列(bitonicsequence)的东西，它的解释貌似有两种，一种是我看见某篇英文论文里说，是先上升后下降或者可以通过循环连接(即最后一个连到第一个)让它变成这样的；还有一种就是中文论文里说的一个从小到大，另一个从大到小的两个序列接在一起构成的序列。当然本质上这两个没有区别，但是第一种解释貌似可以表示更广泛一点的可以连成环来看的情况，有时候中文翻译就是不靠谱啊唉，搞得我一开始理解了半天。
对于一个双调序列我们定义一个它的0-1序列：
当a[i]大于某一个值，它的f值为1，a[i]小于某一个值，它的f值为0，最后所有的f值就是它的0-1序列。所以双调序列的0-1序列一定是000..00111..1100..000或者111..1100..00111..111这样的。
然后构造的是双调排序网络。
有一个叫半清洁器的东西，它长成这样：
半清洁器能够把一个长度为[n]的双调序列变成上下两个长度为[n/2]的双调序列，并且上面的序列中的所有数都不大于下面序列，并且这两个序列中至少有一个是清洁的。所谓清洁，就是只有0或者1组成。它的这个能力是显然的：对于每一个gate，它比较的两个输入一个属于上半序列，另一个属于下半序列，它们中较小的一定从上半序列输出，由于0-1序列中要么是0要么是1并且输入数列双调，所以必然有一个输出半序列清洁。CLRS上有举例证明：
就是以上四种情况。
看到这个半清洁器，就有一种二分的感觉了。
双调排序网络，就是这样构造的：
可以看出，有logn层的半清洁器，
这是n=8的时候的具体构造，很美有木有。
然后一个数列的实例，可以看见它是怎么工作的：
可以看出，当输入的是一个双调序列的时候，它能够正确地排序，但是，如何保证输入总是双调？这显然很困难，那么我们就想到，如果长度为[n]输入是这样：前半段单调不减，后半段也单调不减，如上例中00111000，把后一半颠倒，即序列为00110001，这样是否能够实现正确排序呢？答案是肯定的，我们构造的东西叫做merger，合并网络。它是否有点像mergesort呢，是的！等会会讲到。这里先讲它的构造方法。其实很简单，发现输入的后半段颠倒，那么我们也可以把网络线路的后半段颠倒：
上图：输入的后半段颠倒
上图：线路的后半段（即不同颜色标注的线路）颠倒，颠倒完成（右图）的就是merger[n]
上图：merger[n]的等价构造。
于是总结出merger[n]的构造模式：
flipcleaner[n]就是左侧这个类似侧三角的东西。
于是就要问，构造出merger有什么用呢？
联想mergesort的思想，先两个两个比较，再把上一轮比较的结果两个两个合并，再合并，那么，可以类比利用合并网络！
想想我们构造的merger的功能：把输入进来的前半段单增，有半段也单增的序列，合并成一个单增的序列。这个不就是mergesort里面的合并么！我们只要同样按照merge sort的想法，先两个两个比较，再层层合并，完全可以实现。
所以，总的网络就非常好构造了：
上图：递归构造，层层合并
上图：sorter[8]的具体构造
上图：实例说明sorter[8]的工作。
所以，我们就这样构造了一个gate数为O(n(logn)^2)的，深度（可以看做是排序时间复杂度）为O((logn)^2)的sorter。
-------------------------------END-----------------------------------
再次感叹一句：真的很美有木有！
