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