FPGA實現雙調排序算法的探索與實踐

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

雙調排序（BitonicSort）是數據獨立（Data-independent）的排序算法，即比較順序與數據無關，特別適合并行執行。在了解雙調排序算法之前，我們先來看看什么是雙調序列。

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

（1）如果存在索引號j，其中0≤j

（2）在條件（1）無法滿足的情況下，如果存在索引號i，且0≤i

換言之，序列本身先單調遞增后單調遞減或者序列經過循環移位后先單調遞增再單調遞減，那么該序列就是雙調序列。

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

下圖所示序列滿足條件（2），其中i=4，j=5，循環移位后變為先單調遞增后單調遞減。

上述兩種情形比較簡單，所以也比較容易判斷是否為雙調序列。但其實下面幾種情形都是雙調序列，圖①和圖②不再贅述。圖③“升->降->升”，通過循環移位即可變為先單調遞增再單調遞減序列。圖④“降->升->降”，仍可通過循環移位變為先單調遞增再單調遞減序列。需要注意的是完全單調遞增或者完全單調遞減的序列也是雙調序列，例如(0,1,4,5)和(7,5,3)均為雙調序列。

雙調序列的性質：

（1）雙調序列的子序列仍為雙調序列。

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

（2）將一個雙調序列循環移位后仍為雙調序列

（3）任意兩個實數都可以組成雙調序列

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

Batcher定理：

若序列S為雙調序列，即

令

那么S1和S2仍為雙調序列，且S2中的任意一個元素不小于S1中的任意一個元素。

對一個雙調序列重復使用Batcher定理最終可以得到一個完全單調遞增或單調遞減的序列，也就完成了排序。不難看出，在使用Batcher定理時下一次序列長度總是當前序列長度的一半，因此，雙調排序算法要求序列長度為2的整數次冪。

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

審核編輯：黃飛

?