查看“︁Batcher归并网络”︁的源代码

{{多個問題|
{{cleanup-jargon|time=2018-02-14T22:20:24+00:00}}
{{unreferenced|time=2018-02-14T22:20:24+00:00}}
{{intromissing|time=2010-03-26T06:27:15+00:00}}
}}
{{NoteTA
|G1 = IT
}}
'''Batcher排序网络'''（{{lang-en|Batcher odd–even mergesort}}）是由一系列'''Batcher比较器'''（Batcher's Comparator）组成的。Batcher比较器是指在两个输入端给定输入x,y，再在两个输出端输出最大值max{x,y}和最小值min{x,y}。

'''比较器网络'''是用Batcher比较器连成的完成某一功能的网络。

所谓'''双调序列'''（Bitonic Sequence）是指由一个非严格增序列X和非严格减序列Y（其中X的最小元素正好是Y的最大元素）构成的序列，比如序列（23,10,8,3,5,7,11,78）。

定义：一个序列a1,a2,…,an是'''双调序列'''，如果：
#存在一个ak(1≤k≤n),使得a1≥…≥ak≤…≤an成立；或者
#序列能够循环移位满足条件（1）

== 奇偶归并网络 ==
输入两个已排好序的序列，对这两个序列进行[[归并排序]]，在串行算法中的时间复杂度为O(n)。在并行计算中可以用奇偶归并算法来实现的。以输入的两个4元素有序序列为A和B为例，首先将这两个序列进行'''逆洗牌（Unshuffle）'''得到两个序列：其中一个是由A,B中奇数号元素组成的序列，记作奇序列OM，另一个则是由A,B中偶数号元素组成的序列，记作偶序列序列EM。接着将OM送入（2,2）奇归并器中，将EM送入（2,2）偶归并器中。于是得到一组有序的奇序列和一组有序偶序列。最后除了奇序列一个元素之外将这两个序列进行'''洗牌（Shuffle）比较'''操作即可得到一个有序序列。

算法的递归性：一个n阶的归并器是由两个n/2阶的归并器加一个洗牌比较网络构成的。比如上面的两个（2,2）归并器和最后的洗牌比较网络就构成了一个（4,4）的归并器。

一个四阶奇偶归并的例子：假设归并前的的序列是（1,5,7,6）和（2,3,4,9），那么第一次操作就将（1,2,7,4）送入（2,2）归并器中归并，得到结果为（1,2,4,7）；（5,3,6,9）送入（2,2）归并器中归并，得到结果为（3,5,6,9），接着将这两个排号序的序列进行洗牌比较：(1,3<->2,5<->4,6<->7,9)=>(1,2,3,4,5,6,7,9)。

可以证明这个算法是正确的，我们要用到[[高德纳]]（Donald Ervin Knuth）的[[0-1原理]]，我们发现，对于输入的任意两个有序的0,1序列，奇序列与偶序列正好相差0个，1个或2个0。由于奇序列的第一个元素不参与最后的洗牌比较，所以参与比较的0,1数偶只有0个或1个，所以对0,1序列一定能够得到正确的排序。故而对任意的序列，奇偶归并网络可以产生正确的排序。

== 双调归并网络 ==
双调归并网络是基于'''Batcher定理'''而构建的。'''Batcher定理'''是说将任意一个长为2n的双调序列A分为等长的两半X和Y，将X中的元素与Y中的元素一一按原序比较，即<math>a_i</math>与<math>a_{i+n}(i\le n)</math>比较，将较大者放入MAX序列，较小者放入MIN序列。则得到的MAX和MIN序列仍然是双调序列，并且MAX序列中的任意一个元素不小于MIN序列中的任意一个元素。

根据这个原理，我们可以将一个输入的n元素双调序列首先通过洗牌比较操作得到一个MAX序列和一个MIN序列，然后通过两个n/2阶双调归并器处理就可以得到一个有序序列。

这个算法也是递归的，因为n阶的双调归并器是由一个洗牌比较网络两个n/2阶的双调归并器组成的。

== 参阅 ==
*[[并行计算]]
*[[洗牌交换连接]]
{{算法}}
[[Category:并发计算]]