双调排序（bitonic sort）属于排序网络（Sorting Network）的一种。相较于传统的排序算法，排序网络真正的研究价值在于，假如有机器可以同时处理多个比较器，排序的速度将大幅度提高。简单来说，它是一种可以并行计算的排序算法。

理论的提出

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序列，然后通过两个n/2阶双调归并器处理就可以得到一个有序序列。

参考资料

最新修订时间：2024-05-21 11:17