长度为nnn的序列a1a_1a1,a2a_2a2,—,ana_nan被称为双调序列当且仅当存在1<=k<=n1<=k<=n1<=k<=n满足ak,ak+1,−−−,an,a1,−−−,ak−1a_k,a_{k+1},---,a_n,a_1,---,a_{k-1}ak,ak+1,−−−,an,a1,−−−,ak−1是先单调增后单调减或先单调减后单调增的序列
设nnn为偶数
有如下的Batcher定理:
令ai=min(ai,ai+n/2),ai+n/2=max(ai,ai+n/2)1<=i<=n/2a_i = min(a_i,a_{i+n/2}),a_{i+n/2} = max(a_i,a_{i+n/2}) 1<=i<=n/2ai=min(ai,ai+n/2),ai+n/2=max(ai,ai+n/2)1<=i<=n/2则(ai∣1<=i<=n/2)(a_i|1<=i<=n/2)(ai∣1<=i<=n/2)和(ai+n/2∣1<=i<=n/2)(a_{i+n/2}|1<=i<=n/2)(ai+n/2∣1<=i<=n/2)均为双调序列且前者任意元素均小于等于后者任意元素，当然如果令ai=max(ai,ai+n/2),ai+n/2=min(ai,ai+n/2)1<=i<=n/2a_i = max(a_i,a_{i+n/2}),a_{i+n/2} = min(a_i,a_{i+n/2}) 1<=i<=n/2ai=max(ai,ai+n/2),ai+n/2=min(ai,ai+n/2)1<=i<=n/2则前者任意元素均大于等于后者任意元素
这个定理的证明我不会,希望好心人在评论区给出文献
设nnn为2的幂
得到(ai∣1<=i<=n/2)(a_i|1<=i<=n/2)(ai∣1<=i<=n/2)和(ai+n/2∣1<=i<=n/2)(a_{i+n/2}|1<=i<=n/2)(ai+n/2∣1<=i<=n/2)的操作称为Batcher操作,如果ai=min(ai,ai+n/2),ai+n/2=max(ai,ai+n/2)1<=i<=n/2a_i = min(a_i,a_{i+n/2}),a_{i+n/2} = max(a_i,a_{i+n/2}) 1<=i<=n/2ai=min(ai,ai+n/2),ai+n/2=max(ai,ai+n/2)1<=i<=n/2则称为Batcher_Min操作,否则称为Batcher_Max操作,进行Batcher_Min操作后递归地在(ai∣1<=i<=n/2)(a_i|1<=i<=n/2)(ai∣1<=i<=n/2)和(ai+n/2∣1<=i<=n/2)(a_{i+n/2}|1<=i<=n/2)(ai+n/2∣1<=i<=n/2)上执行Batcher_Min操作称为Batcher_Min排序,进行Batcher_Max操作后递归地在(ai∣1<=i<=n/2)(a_i|1<=i<=n/2)(ai∣1<=i<=n/2)和(ai+n/2∣1<=i<=n/2)(a_{i+n/2}|1<=i<=n/2)(ai+n/2∣1<=i<=n/2)上执行Batcher_Max操作称为Batcher_Max排序,
双调排序:
采用自底向上归并的方法,要求待排序序列sss长度n必须为2的幂
先将sss两两为一组,对每一组交替执行Batcher_Min排序和Batcher_Max排序(第一组执行Batcher_Min排序),结束后奇数组单调增，偶数组单调减,然后将sss每四个为一组,对每一组交替执行Batcher_Min排序和Batcher_Max排序(第一组执行Batcher_Min排序,注意每一次执行排序前前两个元素单调增,后两个元素单调减),结束后奇数组单调增，偶数组单调减,因此类推
.最后将sss每n/2个为一组分成两组,对第一组执行Batcher_Min排序,对第二组执行Batcher_Max排序(注意执行排序前每一组前n/4个元素单调增,后n/4个元素单调减),结束后第一组单调增,第二组单调减.最终为了使sss从小到大有序,我们对整个sss执行Batcher_Min排序,至此sss完全有序,排序结束.
c++实现(该算法非常容易并行化,在cpu,gpu上都是如此，请自己思考，以下只给出cpu上执行的串行代码)
#include<iostream>#include<vector>#include<algorithm>#include<random>usingstd::vector;enumclassop_type{MIN,Max};voidBatcherOperation(vector<longlong>&seq,size_t left,size_t right,size_t k,op_type op)//right-left是2^k{if(k==0)return;size_t gap=1ull<<(k-1);for(size_t i=left;i<left+gap;++i){if(op==op_type::MIN){if(seq[i]>seq[i+gap]){std::swap(seq[i],seq[i+gap]);}}else{if(seq[i]<seq[i+gap]){std::swap(seq[i],seq[i+gap]);}}}BatcherOperation(seq,left,left+gap,k-1,op);BatcherOperation(seq,left+gap,right,k-1,op);}voidgenAndSortBitonicSeq(vector<longlong>&seq,size_t k)//2^k == seq.size(){size_t n=1;while(n<=k){size_t gap=1ull<<n;op_type flag=op_type::MIN;for(size_t i=0;i<seq.size();i=i+gap){BatcherOperation(seq,i,i+gap,n,flag);if(flag==op_type::MIN){flag=op_type::Max;}else{flag=op_type::MIN;}}++n;}}boolBitonicSort(vector<longlong>&seq){if(seq.empty())returntrue;for(size_t i=0;i<seq.size();++i){if(seq[i]==std::numeric_limits<longlong>::max()){std::cerr<<"错误,初始待排序序列不能包含最大可能值"<<std::endl;returnfalse;}}size_t k=0;while((1ull<<k)<seq.size()){++k;}size_t original=seq.size();for(size_t i=0;i<(1ull<<k)-original;++i){seq.push_back(std::numeric_limits<longlong>::max());}genAndSortBitonicSeq(seq,k);seq.erase(seq.begin()+original,seq.end());returntrue;}intmain(){/* vector<long long> seq{10, 20, 5, 9, 3, 8, 12, 14, 90, 0, 60, 40, 23, 35, 95, 18}; BitonicSort(seq); for (size_t i = 0; i < seq.size(); ++i) { std::cout << seq[i] << " "; } std::cout << std::endl;*/constsize_t N=2000;for(size_t i=1;i<=N;++i){vector<longlong>seq(i);for(size_t j=0;j<i;++j){seq[j]=j+1;}vector<longlong>seq_c;seq_c.insert(seq_c.end(),seq.begin(),seq.end());seq_c.insert(seq_c.end(),seq.begin(),seq.end());shuffle(seq_c.begin(),seq_c.end(),std::default_random_engine());if(BitonicSort(seq_c)){std::cout<<"N="<<i<<"排序结果: ";for(size_t j=0;j<seq_c.size();j+=2){if(seq_c[j]!=j/2+1||seq_c[j+1]!=j/2+1){std::cout<<"错误!"<<std::endl;exit(-1);}}std::cout<<"正确!"<<std::endl;}else{std::cerr<<"N="<<i<<"的排序失败"<<std::endl;exit(-1);}}return0;}
