典型的排序算法包括冒泡排序、選擇排序、插入排序、歸并排序、快速排序、希爾排序、計(jì)數(shù)排序、雙調(diào)排序等。這其中，雙調(diào)排序以其高度的并行性著稱，非常適合于在FPGA上實(shí)現(xiàn)。

雙調(diào)排序（BitonicSort）是數(shù)據(jù)獨(dú)立（Data-independent）的排序算法，即比較順序與數(shù)據(jù)無(wú)關(guān)，特別適合并行執(zhí)行。在了解雙調(diào)排序算法之前，我們先來(lái)看看什么是雙調(diào)序列。

雙調(diào)序列（BitonicSequence）的定義：雙調(diào)序列是一個(gè)先單調(diào)遞增后單調(diào)遞減的序列，即存在兩種單獨(dú)特性，故為“雙調(diào)”。從數(shù)學(xué)角度而言，對(duì)于序列(a[0],a[1],…,a[n-1])：

（1）如果存在索引號(hào)j，其中0≤j

（2）在條件（1）無(wú)法滿足的情況下，如果存在索引號(hào)i，且0≤i

換言之，序列本身先單調(diào)遞增后單調(diào)遞減或者序列經(jīng)過(guò)循環(huán)移位后先單調(diào)遞增再單調(diào)遞減，那么該序列就是雙調(diào)序列。

下圖所示序列滿足條件（1），j=5，先單調(diào)遞增后單調(diào)遞減。

下圖所示序列滿足條件（2），其中i=4，j=5，循環(huán)移位后變?yōu)橄葐握{(diào)遞增后單調(diào)遞減。

上述兩種情形比較簡(jiǎn)單，所以也比較容易判斷是否為雙調(diào)序列。但其實(shí)下面幾種情形都是雙調(diào)序列，圖①和圖②不再贅述。圖③“升->降->升”，通過(guò)循環(huán)移位即可變?yōu)橄葐握{(diào)遞增再單調(diào)遞減序列。圖④“降->升->降”，仍可通過(guò)循環(huán)移位變?yōu)橄葐握{(diào)遞增再單調(diào)遞減序列。需要注意的是完全單調(diào)遞增或者完全單調(diào)遞減的序列也是雙調(diào)序列，例如(0,1,4,5)和(7,5,3)均為雙調(diào)序列。

雙調(diào)序列的性質(zhì)：

（1）雙調(diào)序列的子序列仍為雙調(diào)序列。

例如，序列(0,1,4,5,6,7,5,3)其子序列(6,7,5,3)仍為雙調(diào)序列。

（2）將一個(gè)雙調(diào)序列循環(huán)移位后仍為雙調(diào)序列

（3）任意兩個(gè)實(shí)數(shù)都可以組成雙調(diào)序列

（4）如果序列(a[0],…,a[i])是單調(diào)遞增序列，(b[i+1],…,b[n-1])是單調(diào)遞減序列，那么(a[0],…,a[i],b[i+1],…,b[n-1])是一個(gè)雙調(diào)序列

Batcher定理：

若序列S為雙調(diào)序列，即

令

那么S1和S2仍為雙調(diào)序列，且S2中的任意一個(gè)元素不小于S1中的任意一個(gè)元素。

對(duì)一個(gè)雙調(diào)序列重復(fù)使用Batcher定理最終可以得到一個(gè)完全單調(diào)遞增或單調(diào)遞減的序列，也就完成了排序。不難看出，在使用Batcher定理時(shí)下一次序列長(zhǎng)度總是當(dāng)前序列長(zhǎng)度的一半，因此，雙調(diào)排序算法要求序列長(zhǎng)度為2的整數(shù)次冪。

使用Batcher定理，我們可以完成一個(gè)雙調(diào)序列的排序，如下圖所示案例：原始序列長(zhǎng)度為16，第1次分割后產(chǎn)生兩個(gè)序列，每個(gè)序列長(zhǎng)度為8；第2次分割時(shí)，產(chǎn)生4個(gè)序列，每個(gè)序列長(zhǎng)度為4；第3次分割時(shí)，產(chǎn)生8個(gè)序列，每個(gè)序列長(zhǎng)度為2；第4次分割時(shí)，產(chǎn)生16個(gè)序列，每個(gè)序列長(zhǎng)度為1。依據(jù)此規(guī)律可以得出：若序列長(zhǎng)度為2n，那么第i次(i=1,2,…,n)分割時(shí)，會(huì)產(chǎn)生2i個(gè)序列，每個(gè)序列長(zhǎng)度為2(n-i)，要最終完成排序，需要經(jīng)過(guò)n次分割，每次分割需要比較n/2次也就是需要n/2個(gè)比較器，該比較器會(huì)同時(shí)輸出最大值和最小值。

審核編輯：黃飛

?