雙調排序（bitonic sort）屬於排序網路(Sorting Network）的一種。相較於傳統的排序算法，排序網路真正的研究價值在於，假如有機器可以同時處理多個比較器，排序的速度將大幅度提高。簡單來說，它是一種可以並行計算的排序算法。
基本介紹
- 中文名：雙調排序
- 外文名：bitonic sort
- 基本信息：屬於排序網路(Sorting N
- 理論的提出：1968年Batcher提出了
理論的提出
1968年Batcher提出了兩個著名的排序方法：奇偶排序和Bitonic排序，由於該類方法在開關網路，並行處理系統，多訪問存儲系統等方面有著重要的套用價值。
所謂雙調序列(Bitonic Sequence)是指由一個非嚴格增序列X和非嚴格減序列Y構成的序列，比如序列（23,10,8,3,5,7,11,78）。
定義:一個序列a1,a2,…,an是雙調序列(Bitonic Sequence)，如果：
(1)存在一個ak(1≤k≤n), 使得a1≥…≥ak≤…≤an成立；或者
(2)序列能夠循環移位滿足條件(1)
雙調歸併網路是基於Batcher定理而構建的。Batcher定理是說將任意一個長為2n的雙調序列A分為等長的兩半X和Y，將X中的元素與Y中的元素一一按原序比較，即a[i]與a[i+n](i<n)比較，將較大者放入MAX序列，較小者放入MIN序列。則得到的MAX和MIN序列仍然是雙調序列，並且MAX序列中的任意一個元素不小於MIN序列中的任意一個元素。
根據這個原理，我們可以將一個輸入的n元素雙調序列首先通過洗牌比較操作得到一個MAX序列和一個MIN序列，然後通過兩個n/2階雙調歸併器處理就可以得到一個有序序列。
