雙調(diào)排序是data-independent的排序， 即比較順序與數(shù)據(jù)無關(guān)的排序方法， 特別適合做并行計(jì)算，例如用GPU、fpga來計(jì)算。

1、雙調(diào)序列

在了解雙調(diào)排序算法之前，我們先來看看什么是雙調(diào)序列。 雙調(diào)序列是一個(gè)先單調(diào)遞增后單調(diào)遞減（或者先單調(diào)遞減后單調(diào)遞增）的序列。

2、Batcher定理

將任意一個(gè)長(zhǎng)為2n的雙調(diào)序列A分為等長(zhǎng)的兩半X和Y，將X中的元素與Y中的元素一一按原序比較，即a[i]與a[i+n] (i < n)比較，將較大者放入MAX序列，較小者放入MIN序列。則得到的MAX和MIN序列仍然是雙調(diào)序列，并且MAX序列中的任意一個(gè)元素不小于MIN序列中的任意一個(gè)元素[2]。

3、雙調(diào)排序

假設(shè)我們有一個(gè)雙調(diào)序列，則我們根據(jù)Batcher定理，將該序列劃分成2個(gè)雙調(diào)序列，然后繼續(xù)對(duì)每個(gè)雙調(diào)序列遞歸劃分，得到更短的雙調(diào)序列，直到得到的子序列長(zhǎng)度為1為止。這時(shí)的輸出序列按單調(diào)遞增順序排列。

見下圖：升序排序，具體方法是，把一個(gè)序列(1…n)對(duì)半分，假設(shè)n=2^k，然后1和n/2+1比較，小的放上，接下來2和n/2+2比較，小的放上，以此類推；然后看成兩個(gè)(n/2)長(zhǎng)度的序列，因?yàn)樗麄兌际请p調(diào)序列，所以可以重復(fù)上面的過程；總共重復(fù)k輪，即最后一輪已經(jīng)是長(zhǎng)度是2的序列比較了，就可得到最終的排序結(jié)果。

雙調(diào)排序示意圖[1]:

4、任意序列生成雙調(diào)序列

前面講了一個(gè)雙調(diào)序列如何排序，那么任意序列如何變成一個(gè)雙調(diào)序列呢？

這個(gè)過程叫Bitonic merge, 實(shí)際上也是divide and conquer的思路。 和前面sort的思路正相反， 是一個(gè)bottom up的過程——將兩個(gè)相鄰的，單調(diào)性相反的單調(diào)序列看作一個(gè)雙調(diào)序列， 每次將這兩個(gè)相鄰的，單調(diào)性相反的單調(diào)序列merge生成一個(gè)新的雙調(diào)序列， 然后排序（同3、雙調(diào)排序）。 這樣只要每次兩個(gè)相鄰長(zhǎng)度為n的序列的單調(diào)性相反， 就可以通過連接得到一個(gè)長(zhǎng)度為2n的雙調(diào)序列，然后對(duì)這個(gè)2n的序列進(jìn)行一次雙調(diào)排序變成有序，然后在把兩個(gè)相鄰的2n序列合并（在排序的時(shí)候第一個(gè)升序，第二個(gè)降序）。 n開始為1， 每次翻倍，直到等于數(shù)組長(zhǎng)度， 最后就只需要再一遍單方向（單調(diào)性）排序了。

以16個(gè)元素的array為例，

相鄰兩個(gè)元素合并形成8個(gè)單調(diào)性相反的單調(diào)序列，

兩兩序列合并，形成4個(gè)雙調(diào)序列，分別按相反單調(diào)性排序

4個(gè)長(zhǎng)度為4的相反單調(diào)性單調(diào)序列，相鄰兩個(gè)合并，生成兩個(gè)長(zhǎng)度為8的雙調(diào)序列，分別排序

2個(gè)長(zhǎng)度為8的相反單調(diào)性單調(diào)序列，相鄰兩個(gè)合并，生成1個(gè)長(zhǎng)度為16的雙調(diào)序列，排序

示意圖[1]：

詳細(xì)Bitonic merge圖（本圖只畫到生成一個(gè)16長(zhǎng)的雙調(diào)序列，最后排序沒有畫出）：

最后再放一個(gè)8個(gè)元素排序的示意圖[5]：

5、非2的冪次長(zhǎng)度序列排序

這樣的雙調(diào)排序算法只能應(yīng)付長(zhǎng)度為2的冪的數(shù)組。那如何轉(zhuǎn)化為能針對(duì)任意長(zhǎng)度的數(shù)組呢？一個(gè)直觀的方法就是使用padding。即使用一個(gè)定義的最大或者最小者來填充數(shù)組，讓數(shù)組的大小填充到2的冪長(zhǎng)度，再進(jìn)行排序。最后過濾掉那些最大（最小）值即可。這種方式會(huì)使用到額外的空間，而且有時(shí)候padding的空間比較大（如數(shù)組長(zhǎng)度為1025個(gè)元素，則需要填充到2048個(gè)，浪費(fèi)了大量空間）。但是這種方法比較容易轉(zhuǎn)化為針對(duì)GPU的并行算法。所以一般來說，并行計(jì)算中常使用雙調(diào)排序來對(duì)一些較小的數(shù)組進(jìn)行排序[3]。 如果要考慮不用padding，用更復(fù)雜的處理方法，參考[4] n!=2^k的雙調(diào)排序網(wǎng)絡(luò)，本文略。

參考資料

• [1] CUDA(六). 從并行排序方法理解并行化思維——冒泡、歸并、雙調(diào)排序的GPU實(shí)現(xiàn), http://blog.csdn.net/abcjennifer/article/details/47110991
• [2] 并行計(jì)算】Bitonic Sort（雙調(diào)排序）基礎(chǔ), http://blog.csdn.net/jiange_zh/article/details/49533477
• [3] 雙調(diào)排序：從串行到并行，以及OpenCL上的實(shí)現(xiàn), http://blog.csdn.net/bryanlai0720/article/details/45094675
• [4] n!=2^k的雙調(diào)排序網(wǎng)絡(luò), http://blog.csdn.net/ljiabin/article/details/8630627
• [5] 分段雙調(diào)排序?qū)崿F(xiàn), http://blog.csdn.net/u014226072/article/details/56840243

---

原文：https://blog.csdn.net/xbinworld/article/details/76408595

MARSGGBO?原創(chuàng)2019-1-3

總結(jié)

以上是生活随笔為你收集整理的bucket sort sample sort 并行_双调排序Bitonic Sort，适合并行计算的排序算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。