Batcher归并网络
維基百科,自由的 encyclopedia
Batcher排序网络(英語:Batcher odd–even mergesort)是由一系列Batcher比较器(Batcher's Comparator)组成的。Batcher比较器是指在两个输入端给定输入x,y,再在两个输出端输出最大值max{x,y}和最小值min{x,y}。
比较器网络是用Batcher比较器连成的完成某一功能的网络。
所谓双调序列(Bitonic Sequence)是指由一个非严格增序列X和非严格减序列Y(其中X的最小元素正好是Y的最大元素)构成的序列,比如序列(23,10,8,3,5,7,11,78)。
定义:一个序列a1,a2,…,an是双调序列,如果:
- 存在一个ak(1≤k≤n),使得a1≥…≥ak≤…≤an成立;或者
- 序列能够循环移位满足条件(1)