双调排序（Bitonic Sort）

· · 个人记录

前言

双调排序（\text{Bitonic Sort}）是一种比较顺序与数据无关的排序算法，其比较和交换操作只依赖于简单的比较器，非常适合被并行化处理，故而常用于 \text{GPU} 编程。

于 \text{1968} 年由 \text{Batcher} 提出。

时间复杂度为 O(n\log_2^2n) 。

虽然其时间复杂度乍一看不如快排等著名排序快，但当双调排序应用于并行处理时，其时间复杂度就变成了 O(\log_2^2n) 。而快排却并不容易被改成并行处理的模式，因为快排的比较情况不能预先确定。

就算法竞赛而言，双调排序用处不大。

但双调排序真的是个很优美的算法，君且听我娓娓道来。

前置知识和约定

关于本博客的图片

都是我自己用“画图”画出来的。。。

画质粗糙还请体谅一下。。。

关于本博客的证明

证明都是我自己想的，如果您发现我的逻辑上有 \text{bug} 还请在评论中斧正，我尽快修改。

比较器

本篇博客中的图片均用“ \large\red\downarrow ”来表示一个比较器，比较器作用的结果是：将竖线连接的两个位置上的数进行比较，并将较大的数放到箭头所指向的位置上。

如：

表示将 a_3 与 a_5 进行比较，并把较大的数放到 a_5 里，较小的数放到 a_3 里。

再如：

是一个可以对三个元素排序的冒泡排序。

可以看出，比较器是一个很简单的计算结构。

双调序列（\text{Bitonic Sequence}）

若一个序列满足以下两个条件之一：

  2. 序列能够通过循环位移满足 1 。

循环位移就是每次将序列最后一个元素放到最前面去，这样执行若干次。

需要注意的是，单调不降和单调不升的序列都属于双调序列。

\text{Batcher} 定理

定理内容

将一个长度为 2n 双调序列划分为等长的两半 X,Y ，将 X 与 Y 中的元素按原顺序一一比较（即 a_i 与 a_{i+n} 比较，i=1,2,\cdots,n），较大的放入 MAX 序列，较小的放入 MIN 序列，则 MAX,MIN 两个序列均仍为双调序列，且 MAX 中所有元素均大于等于 MIN 中任意元素。

即：

为了方便叙述，我将这个操作称为“双调分裂（\text{Bitonic Split}）”。

定理证明

因为循环位移并不会改变这 n 对被比较的元素且不改变序列是否双调的性质，故对第二种情况的双调序列的研究一定可等效为对第一种情况的双调序列的研究，所以在此只证明定理对第一种情况的双调序列成立。

而对于第二种情况的双调序列，只需要先循环位移，使之变为第一种，完成双调分裂后，再将 MAX,MIN 序列分别循环位移回去。易知这个过程不会改变序列双调与否，也不会改变元素本来应该在的位置。所以所证明的定理依然成立。

于是 \text{Batcher} 定理得证。

双调排序的实现

双调合并（\text{Bitonit Merge}）

有了 \text{Batcher} 定理，我们立刻就能得到将一个长度为 2^n 的双调序列变成单调序列的做法。

只需将双调序列分裂，对得到的两个双调序列继续双调分裂。直到序列长度为 1 。

由于每次操作都会使双调序列中较大的那一半的数放到一起，较小那一半放到另一边。故不断分裂后总会得到一个单调序列。

即：

像这样将一个双调序列转化为单调序列的操作被称为“双调合并（\text{Bitonic Merge}）”。

双调排序

有了双调合并，我们就可以构造双调排序的算法。

上述双调合并可将双调序列转化为单调不降序列。

我们把双调合并的 \large\red\downarrow 比较节点，改为 \large\red\uparrow ，就可以把双调序列转化为单调不增序列。这两个序列拼起来，就又是一个更大的双调序列。

所以我们得到了将两个双调序列合并为一个双调序列的操作。

这样，我们就可以实现分治了。

具体而言：

像这样：

橙色、绿色框均能够将双调序列分裂。

根据上文论述，如图这样比较、交换，最终会得到一个单调不降的序列。

为了便于 \text{GPU} 编程，有时候也会将上图改为：

（看我手工画图厉害吧）

图中所有的比较节点均为原先的 \large\red\downarrow ，本质上与原来的没什么区别，只是等效于将单调不增的那些序列全部翻转，变成单调不降的序列。

这样比较器的方向就全部一致了。

把这张图翻译成代码，即为：

void Bitonic_Sort(int a[],const int N) { // N 为数据总数，须为 2的幂次。
    int t;
    for(int i=1,i2=2;i2<=N;++i,i2<<=1) {
        for(int j=1,j2=i2-1;j2>=1;++j,j2-=2) {
            for(int k=j;k<=N;k+=i2) { 
                if(a[k]<a[k+j2]) t=a[k],a[k]=a[k+j2],a[k+j2]=t;
            }
        }
        for(int j=(i2>>2);j>=1;j>>=1) {
            for(int k=1;k<=j;++k) {
                for(int l=k;l<=N;l+=(j<<1)) {
                    if(a[l]<a[l+j]) t=a[l],a[l]=a[l+j],a[l+j]=t;
                }
            }
        }
    }
}

双调排序的优缺点

优点

缺点

后记