基于Batcher比较器的双调排序网络

深碍√TFBOYSˉ_ 2022-02-02 13:47 120阅读 0赞

1. Batcher比较器

Batcher比较器是指如果在两个输入端给定输入x,y，再在两个输出端输出最大值max\{x,y\}和最小值min\{x,y\}。如图1所示，我们规定Batcher比较器的上输出端输出最小值，下输出端输出最大值。

![942216-20160702104145187-896381355.png][]

2. 双调序列

所谓**双调序列(Bitonic Sequence)**是指由一个非严格增序列X和非严格减序列Y（其中X的最小元素正好是Y的最大元素）构成的序列，比如序列（23,10,8,3,5,7,11,78）。23,10,8为减序列，8,3,5,7,11,78为增序列，8为中间元素。具体的数学定义是酱紫de:

定义:一个序列a1,a2,…,an是**双调序列(Bitonic Sequence)**，如果

(1)存在一个ak(1≤k≤n), 使得a1≥…≥ak≤…≤an成立；或者

(2)序列能够循环移位满足条件(1)

总的来说，双调序列存在一个中间元素，该元素左边为一个增序列（或减序列），右边为一个减序列（或增序列）。如图2所示（向下和向上的斜线分别表示减序列和增序列）：

![942216-20160702104223499-2109284997.png][]

3. Batcher定理

**Batcher定理**是说将任意一个长为2n的双调序列A从中间切成两半，分成等长的两个序列X和Y，然后X和Y相同位置的元素xi与yi比较，小的放到Min序列，大的放到Max序列。由此得到的Max序列和Min序列也是双调序列。且Min序列的每个元素小于或等于Max序列的每个元素。如图3所示：

![942216-20160703095110984-1758809502.png][]

4. 基于Batcher定理的双调归并网络

利用Batcher定理，我们可以将任意一个长为2n的双调序列A划分成Min序列和Max序列，再分别对Min序列和Max序列进行划分，以此类推，直到n=1。最后再将所有含两个元素的子序列归并成完全有序的序列。如图4所示：

![942216-20160703113957640-1864463710.png][]

5. 双调排序网络

双调归并网络的输入必须是双调序列。如果要将其变成任意输入序列的排序网络，那么首先需要将输入序列转换成一个双调序列。主要思想是：将长度为2n的序列看成n个2个元素的有序序列，任意两个有序序列都可以组成一个4元素双调序列，则可以得到n/2个4元素的双调序列；4元素的双调序列通过一个4个输入的双调归并网络即可得到一个4元素的有序序列；两个4元素的有序序列又可以组成一个8元素的双调序列，再经过一个8输入的双调归并网络即可得到一个8元素的有序序列；以此类推，直到最后得到一个2n个元素的有序序列。如图5所示：

![942216-20160703151451046-245980805.png][]

[942216-20160702104145187-896381355.png]: /images/20220202/32e6322968d3423c912ff9c91afbc4db.png
[942216-20160702104223499-2109284997.png]: /images/20220202/3c9a47ed9bbe40fa9d74115e01e66d52.png
[942216-20160703095110984-1758809502.png]: /images/20220202/e9ce7c1ca126401688228008c735caef.png
[942216-20160703113957640-1864463710.png]: /images/20220202/efad33c4fc9044e6bf9c6c5667f1d089.png
[942216-20160703151451046-245980805.png]: /images/20220202/3901f458bafd439092b1aa82d85b2581.png