Bitonic Sort双调排序

这个排序的名字很好玩, Bi是双的意思 tonic是音乐的元音. 所以叫双调, 就是两个调性(递增 递减). 具体的操作可以看 https://en.wikipedia.org/wiki/Bitonic_sorter

我主要讲讲下面这个例子:

[5,2,1,7,3,8,6,4], len = 8

第一步先临近的两个元素比大小, 比如[5,2]变成[2,5], [1,7]变成[7,1], 数组变为

[2,5], [7,1], [3,8], [6,4]

此时序列为[2,5,7,1,3,8,6,4]

这样就是递增, 递减, 递增 递减的两对儿双调.然后就是合并两个双调. 合并的方法是用的wiki中的batcher理论. 显示四个为一组合并, 然后是两个为一组合并.

四个为一组:

[2,1,7,5] ([2,5]和[7,1]合并的结果)

[6,8,3,4] ([3,8]和[6,4]合并的结果)

此时的序列为[2,1,7,5,6,8,3,4]

此时, 并不是双调序列, 还需要进行两个为一组的合并.

[2,1,7,5] 变成 [1,2,5,7] 递增

[6,8,3,4] 变成 [8,6,4,3] 递减,

此时序列为[1,2,5,7,8,6,4,3]

最后要进行八个一组的合并, 然后是四个一组, 然后是两个一组.

八个一组后: [1,2,4,3,8,6,5,7]

四个一组后: [1,2,4,3,5,6,8,7]

两个一组后: [1,2,3,4,5,6,7,8] (已排序)

可见这个排序的递归都是幂次数增长的. 虽然wiki中说这种运算是在并行下使用居多(GPS/FPGA, 等) 但是我觉得这个算法对密集型小量数字排序比较快, 当序列很长时候, 递归次数太多还是扛不住. 而且这个排序只能对2^n的数组做排序, 所以如果缺数字还需要padding

#include <stdio.h>
#include <algorithm>
using namespace std;
void comp(int a[], int i, int j, int asc)
{
    if(asc == (a[i] > a[j])) 
    // low <= i < j < low + k, 
    //if a[i] > a[j](descending) and asc = 1(ascending), we need to swap 
    {
        swap(a[i], a[j]);
    }
}
void merge(int a[], int left, int n, int asc)
{
    if (n > 1)
    {
        int k = n / 2;
        for (int i = left; i < left + k; i++)
        {
            comp(a, i, i+k, asc);
        }
        merge(a, left, k, asc);
        merge(a, left + k, k, asc);        
    }
    
}
void rec(int a[], int left, int n, int asc) 
{
    if(n > 1)
    {
        int k = n / 2;
        rec(a, left, k, 1); // ascending
        rec(a, left + k, k, 0); //decending
        merge(a, left, n, asc); //merge two bitnoic sort
    }
}

void sort(int a[], int n, int ascending) 
{
    rec(a, 0, n, ascending);
}