Bitonic Sort(双调排序)的数学原理是什么？解决办法
Bitonic Sort(双调排序)的数学原理是什么？
网上的文献似乎都在互相抄袭，不是数学符号有错误，就是文献不完整。
下图只说明了如何实现双调排序，原理没看明白。
请明白人给其中的数学原理说一说。
------解决方案--------------------
这是非递归的版本，你要看原始的递归版本才好理解。
------解决方案--------------------
没看明白，这样到底需要多少次交换？复杂度是N*logN吗？
------解决方案--------------------
每次处理的规模为一个区，可以看到这个区初始时，有一个递增序列，一个递减序列。
然后依次对递增序列和递减序列的的元素进行比较和交换，如下图：
两个序列无论是图中哪种情况，最终的结果都是：原来递增序列的内存，存放的是较小的那一半，递减序列的内存，存放了较大的那一半。然后递归……
可能你要问了，为什么要这种双调序列，两个同向单调的不行吗？答案是不行，例如一个1,3，一个2,4，进行比较，1和3比，2和4比，都不需要交换，但是2需要放在前面半个区域。双调就很好的满足了这种性质。
算法的复杂度是O(n*logn*logn)，但是因为操作内存非常规整，适合并行计算。
------解决方案--------------------
第一眼看感觉这个算法好神奇，再看发现跟排序网络好像。
------解决方案--------------------
感觉跟归并排序差不多，把归并排序写成非递归的形式就是这样的吧
------解决方案--------------------
要明白原理的话，看算法导论P704页开始，从排序网络开始。话说不是几句话说的清楚
网上的文献似乎都在互相抄袭，不是数学符号有错误，就是文献不完整。
下图只说明了如何实现双调排序，原理没看明白。
请明白人给其中的数学原理说一说。
------解决方案--------------------
这是非递归的版本，你要看原始的递归版本才好理解。
------解决方案--------------------
没看明白，这样到底需要多少次交换？复杂度是N*logN吗？
------解决方案--------------------
每次处理的规模为一个区，可以看到这个区初始时，有一个递增序列，一个递减序列。
然后依次对递增序列和递减序列的的元素进行比较和交换，如下图：
两个序列无论是图中哪种情况，最终的结果都是：原来递增序列的内存，存放的是较小的那一半，递减序列的内存，存放了较大的那一半。然后递归……
可能你要问了，为什么要这种双调序列，两个同向单调的不行吗？答案是不行，例如一个1,3，一个2,4，进行比较，1和3比，2和4比，都不需要交换，但是2需要放在前面半个区域。双调就很好的满足了这种性质。
算法的复杂度是O(n*logn*logn)，但是因为操作内存非常规整，适合并行计算。
------解决方案--------------------
第一眼看感觉这个算法好神奇，再看发现跟排序网络好像。
------解决方案--------------------
感觉跟归并排序差不多，把归并排序写成非递归的形式就是这样的吧
------解决方案--------------------
要明白原理的话，看算法导论P704页开始，从排序网络开始。话说不是几句话说的清楚