Batcher双调排序及其实现

长度为nnn的序列a1a_1a1​,a2a_2a2​,—,ana_nan​被称为双调序列当且仅当存在1kn1kn1kn满足ak,ak1,−−−,an,a1,−−−,ak−1a_k,a_{k1},---,a_n,a_1,---,a_{k-1}ak​,ak1​,−−−,an​,a1​,−−−,ak−1​是先单调增后单调减或先单调减后单调增的序列设nnn为偶数有如下的Batcher定理:令aimin(ai,ain/2),ain/2max(ai,ain/2)1in/2a_i min(a_i,a_{in/2}),a_{in/2} max(a_i,a_{in/2}) 1in/2ai​min(ai​,ain/2​),ain/2​max(ai​,ain/2​)1in/2则(ai∣1in/2)(a_i|1in/2)(ai​∣1in/2)和(ain/2∣1in/2)(a_{in/2}|1in/2)(ain/2​∣1in/2)均为双调序列且前者任意元素均小于等于后者任意元素当然如果令aimax(ai,ain/2),ain/2min(ai,ain/2)1in/2a_i max(a_i,a_{in/2}),a_{in/2} min(a_i,a_{in/2}) 1in/2ai​max(ai​,ain/2​),ain/2​min(ai​,ain/2​)1in/2则前者任意元素均大于等于后者任意元素这个定理的证明我不会,希望好心人在评论区给出文献设nnn为2的幂得到(ai∣1in/2)(a_i|1in/2)(ai​∣1in/2)和(ain/2∣1in/2)(a_{in/2}|1in/2)(ain/2​∣1in/2)的操作称为Batcher操作,如果aimin(ai,ain/2),ain/2max(ai,ain/2)1in/2a_i min(a_i,a_{in/2}),a_{in/2} max(a_i,a_{in/2}) 1in/2ai​min(ai​,ain/2​),ain/2​max(ai​,ain/2​)1in/2则称为Batcher_Min操作,否则称为Batcher_Max操作,进行Batcher_Min操作后递归地在(ai∣1in/2)(a_i|1in/2)(ai​∣1in/2)和(ain/2∣1in/2)(a_{in/2}|1in/2)(ain/2​∣1in/2)上执行Batcher_Min操作称为Batcher_Min排序,进行Batcher_Max操作后递归地在(ai∣1in/2)(a_i|1in/2)(ai​∣1in/2)和(ain/2∣1in/2)(a_{in/2}|1in/2)(ain/2​∣1in/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上执行的串行代码)#includeiostream#includevector#includealgorithm#includerandomusingstd::vector;enumclassop_type{MIN,Max};voidBatcherOperation(vectorlonglongseq,size_t left,size_t right,size_t k,op_type op)//right-left是2^k{if(k0)return;size_t gap1ull(k-1);for(size_t ileft;ileftgap;i){if(opop_type::MIN){if(seq[i]seq[igap]){std::swap(seq[i],seq[igap]);}}else{if(seq[i]seq[igap]){std::swap(seq[i],seq[igap]);}}}BatcherOperation(seq,left,leftgap,k-1,op);BatcherOperation(seq,leftgap,right,k-1,op);}voidgenAndSortBitonicSeq(vectorlonglongseq,size_t k)//2^k seq.size(){size_t n1;while(nk){size_t gap1ulln;op_type flagop_type::MIN;for(size_t i0;iseq.size();iigap){BatcherOperation(seq,i,igap,n,flag);if(flagop_type::MIN){flagop_type::Max;}else{flagop_type::MIN;}}n;}}boolBitonicSort(vectorlonglongseq){if(seq.empty())returntrue;for(size_t i0;iseq.size();i){if(seq[i]std::numeric_limitslonglong::max()){std::cerr错误,初始待排序序列不能包含最大可能值std::endl;returnfalse;}}size_t k0;while((1ullk)seq.size()){k;}size_t originalseq.size();for(size_t i0;i(1ullk)-original;i){seq.push_back(std::numeric_limitslonglong::max());}genAndSortBitonicSeq(seq,k);seq.erase(seq.begin()original,seq.end());returntrue;}intmain(){/* vectorlong 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 N2000;for(size_t i1;iN;i){vectorlonglongseq(i);for(size_t j0;ji;j){seq[j]j1;}vectorlonglongseq_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::coutNi排序结果: ;for(size_t j0;jseq_c.size();j2){if(seq_c[j]!j/21||seq_c[j1]!j/21){std::cout错误!std::endl;exit(-1);}}std::cout正确!std::endl;}else{std::cerrNi的排序失败std::endl;exit(-1);}}return0;}