学步园

主要参考 http://www.cs.rutgers.edu/~venugopa/parallel_summer2012/bitonic_overview.html

双调排序的时间复杂度是 O(n （logn）^2)，这是说的串行的时间复杂度。这个算法的好处是可以很容易的实现并行，用多个核的并行运算提速，会比串行排序（快排等）要加速很多。

首先要清楚什么是双调序列。是指一个序列前段是升序或者降序，后段是降序或者升序。那么对于任意两个数，都是双调序列。

基本的双调排序只能处理2^n个数的序列。

首先我们定义一个操作是sortSeq, 输出是一个双调序列，其中前半段s1是升序，后半段s2是降序，设这个序列的长度是n,那么s1的元素是<a0,a1,..,an/2-1>,s2的元素是<an/2,an/2+1,..,an>

对s1和s2按照元素的对应位置进行如下操作：

如果a0 <= an/2, 那么不进行操作，否则交换两个元素

用形式化的表示就是：

交换之后，s1中的序列就是两两比较较小的值，s2的序列就是两两比较较大的值

本来s1是升序，s2是降序的，经过如此操作之后，s1也是双调的，s2也是双调的

大家可以看出在构建s1和s2时，可以用n/2个线程对两两元素进行比较交换，从而实现并行运算

再对s1进行sortSeq操作，对s2进行sortSeq操作

就这样递归操作，知道传入sortSeq的序列长度为2

最终s就是升序排列的

那么如何构建最初的双调序列？

算法采用从低向上的方法逐步构建双调序列

对于无序数组，A，相邻的两个数肯定是双调序列，比如(a0,a1), (a2,a3)等等

首先对a0,a1传入sortSeq，变成升序序列，a2,a3传入sortSeq，变成降序序列，a4,a5变成升序序列.....

接下来步长变为4，a0,a1,a2,a3是双调序列，传入sortSeq变成升序序列，a4,a5,a6,a7也是双调的，传入sortSeq变成降序序列

.....

最后步长是n，前n/2元素是升序，后n/2是降序，传入sortSeq变成升序序列

至此算法完成

算法如上图所示，左边是无序的输入序列，右边是输出序列，中间的是排序网络，两个圈连接的是比较器，

图上所示还差最后一步的sortSeq,将其变成升序序列

#include <stdlib.h>
#include <stdio.h>
#include <iostream>
#include <math.h>
#include <time.h>
#include <functional>
#include <algorithm>

using namespace std;

//
void sortSeq(int *arr, int len, bool ascend) {
    int step = len/2;
    for (;step >0 ;step /= 2) {
        for (int i = 0; i < len; i += 2*step) {
            for (int k = 0; k < step; ++k) {
                
                if (ascend) {
                    if (arr[i + k] > arr[i + step +k]) swap(arr[i +k], arr[i+ step + k]);
                }
                else {
                    if (arr[i + k] < arr[i + step +k]) swap(arr[i +k], arr[i+ step + k]);
                }
            }
        }
    }
}

void printvec(int *arr, int len) {
    for (int i = 0; i < len;++i) {
        cout << arr[i] <<"\t";
    }
    cout << endl;
}

int main(int argc, char *argv[]) {
    if (argc != 3) {
        cout << "len a|d\n";
        return 1;
    }
    int len = atoi(argv[1]);
    bool asd = argv[2][0] == 'a' ? true : false;
    int *arr = (int*)malloc(sizeof(int)*len);
    srand((unsigned)time(NULL));
    for (int i = 0; i < len; ++i) arr[i] = rand()%len;
    printvec(arr, len);
   
    
    for (int step = 2; step <= len; step *= 2) {
        for (int i = 0; i < len; i += 2*step) {
            sortSeq(arr + i, step, asd);//升序
           
            if (i + step < len) {
                sortSeq(arr + i + step, step, !asd);//逆序
                
            }
        }
    }
    printvec(arr, len);

    free(arr);
    return 1;
}

如果元素个数不满足2^n次方呢？

http://blog.csdn.net/ljiabin/article/details/8630627

排序网络

n!=2^k的双调排序网络

经典的双调排序网络的设计是用来解决输入长度n=2^k的情况。下面提出了一种对于任意n的双调排序网络算法，它的正确性来自于0-1原理。

问题：

对于长度为n=2^k的双调排序网络包含如表1所示的三块。左边两块是双调排序网络，把原序列均分为两半，分别按升序和降序排列；右边一块是双调合并网络，归并两半有序序列，得到整个有序序列。

图1：双调排序（2^k）的结构

基础定义：

定义：a = a0,…,a(n-1)是一个0-1序列。

    当序列只包含0时，我们称a为清洁的0序列，即a0,…,a(n-1) = 0.

    当序列只包含1时，我们称a为清洁的1序列，即a0,…,a(n-1) = 1.

    如果a序列是由一个清洁的0序列后接一个清洁的1序列构成的，那么我们称a单调递增，即a0,…,a(k-1) = 0, ak,…,a(n-1) = 1.

    如果a序列是由一个清洁的1序列后接一个清洁的0序列构成的，那么我们称a单调递减，即a0,…,a(k-1) = 1, ak,…,a(n-1) = 0.

如果a序列依次由一个清洁的0序列、一个清洁的1序列和一个清洁的0序列构成，那么我们称a序列双调递增，即a0,…,a(k-1)= 0, ak,…,a(m-1) = 1, am,…,a(n-1) = 0.

如果a序列依次由一个清洁的1序列、一个清洁的0序列和一个清洁的1序列构成，那么我们称a序列双调递减，即a0,…,a(k-1)= 1, ak,…,a(m-1) = 0, am,…,a(n-1) = 1.

根据这个定义，一个清洁的序列既可以被称作单调递增，也可以被称作单调递减。相似的，一个单调序列既可以被称作双调递增，也可以被称作双调递减。图2展示了双调序列的一些例子，其中，白色部分代表0，灰色部分代表1，箭头代表特殊情况关系（如清洁的0序列是双调递增序列的一种特殊情况）。

图2：双调序列的例子

定理：设定a是一个0-1序列，如果a是一个清洁的0/1序列或单调递增/减序列或双调递增/减序列，那么a的子序列a’也是。

想法：

标准的双调排序使用了比较网络Bp（p=2^k），我们根据比较网络Bp推导出对于任意n的网络Bn，p是大于的第一个2的幂次方，然后仅仅对n-p/2的元素使用比较网络。图3展示了n=6时的比较网络Bn，把它嵌入到p=8的比较网络Bp，仅仅使用了前两个比较器。

图3：比较网络Bp应用于长度为n的双调递减0-1序列a

定理：n!=2^k，p是大于n的最小的2的幂次方，对双调递减0-1序列a应用比较网络Bn，产生序列b和c具有以下特性（图3中）：

|b| = p/2, b =2^k，

对任意I，j有bi <= cj，

b是双调序列，c是双调递减序列。

证明：如果输入的长度为n的双调递减a被用1填充为长度为p的序列a’，那么这个序列仍保持双调递减。应用比较网络Bp将产生两个双调序列b和c’，|b| = p/2，对于任意i和j，bi <= cj（见标准双调排序）。由于填充的1保持在末尾不变，所以c’双调递减。如果不考虑后面填充的1，序列c’的子序列c也是双调递减。后面属于Bp却不属于Bn的比较是多余的，因此网路Bn应用于序列a会得到同样的结果。

根据这个定理，应用于双调序列b的比较网络Bp（p=2^n）和应用于双调递减序列c的网络Bn（n任意）的递归程序将产生一个有序序列。

如果排序的方向是递减而非递增，这个定理同样适用于“双调递增”而非“双调递减”。证明时，原序列a用0而非1来填充。

最开始，一个序列通过对前一半递减排序对后一半递增排序得到一个双调递减序列。图4展示了对任意输入长度n的双调排序网络的结构图，由于这个网络对每一个0-1序列排序，根据0-1原理它对任意长度的0-1序列排序。

图4：对任意输入长度n的双调排序结构图

程序：

下面的程序实现了对于任意输入长度n的双调排序

数组b通过双调排序排序。

[java] view plaincopy
public class BitonicSorterForArbitraryN implements Sorter  
{  
    private int[] a;  
    private final static boolean ASCENDING=true;    // sorting direction  
   
    public void sort(int[] a)  
    {  
        this.a=a;  
        bitonicSort(0, a.length, ASCENDING);  
    }  
   
    private void bitonicSort(int lo, int n, boolean dir)  
    {  
        if (n>1)  
        {  
            int m=n/2;  
            bitonicSort(lo, m, !dir);  
            bitonicSort(lo+m, n-m, dir);  
            bitonicMerge(lo, n, dir);  
        }  
    }  
   
    private void bitonicMerge(int lo, int n, boolean dir)  
    {  
        if (n>1)  
        {  
            int m=greatestPowerOfTwoLessThan(n);  
            for (int i=lo; i<lo+n-m; i++)  
                compare(i, i+m, dir);  
            bitonicMerge(lo, m, dir);  
            bitonicMerge(lo+m, n-m, dir);  
        }  
    }  
   
    private void compare(int i, int j, boolean dir)  
    {  
        if (dir==(a[i]>a[j]))  
            exchange(i, j);  
    }  
   
    private void exchange(int i, int j)  
    {  
        int t=a[i];  
        a[i]=a[j];  
        a[j]=t;  
    }  
   
    private int greatestPowerOfTwoLessThan(int n)  
    {  
        int k=1;  
        while (k<n)  
            k=k<<1;  
        return k>>1;  
    }  
   
}  

网络：

例如，图5展示了输入长度为6的双调排序网络。

图5：输入长度为6的双调排序网络

分析：

这个对于任意n的新排序网络可以嵌入原始的对于2^k的双调排序网络。因此，它仍有 log(n) · (log(n) + 1) / 2 层，每层最多比较n/2次，结果是一个复杂度为O(nlog(n)^2)的比较器，跟原始的双调排序网络一样。