标准方法在互联网上很容易找到只需在判断左右序列元素相对大小的if语句的一个分支上累加逆序数即可新的方法判断逻辑更为复杂,虽然可以得到正确的结果但代码难以理解不便于维护不是最佳实践仅供参考。#includeiostream#includevector#includerandom#includealgorithmusingnamespacestd;voidmerge(vectorintseq,size_t left,size_t right,size_t mid,size_tReverseOrderPairNum,vectorintassist){size_t run_leftleft;size_t run_rightmid1;size_t runleft;boolpre_biggertrue;while(run_leftmidrun_rightright){if(seq[run_left]seq[run_right]){if(pre_bigger){ReverseOrderPairNum;}else{ReverseOrderPairNumrun_right-mid;pre_biggertrue;}assist[run]seq[run_right];}else{if(pre_biggerfalse){ReverseOrderPairNumrun_right-mid-1;}assist[run]seq[run_left];pre_biggerfalse;}}if(run_leftmid){assist[run]seq[run_left];ReverseOrderPairNum(mid-run_left1)*(right-mid);while(run_leftmid){assist[run]seq[run_left];}}while(run_rightright){assist[run]seq[run_right];}for(size_t ileft;iright;i){seq[i]assist[i];}}size_tgetReverseOrderPairNum(vectorintseq,size_t left,size_t right,vectorintassist){if(leftright)return0;size_t mid(leftright)/2;size_t ReverseOrderPairNum0;ReverseOrderPairNumgetReverseOrderPairNum(seq,left,mid,assist);ReverseOrderPairNumgetReverseOrderPairNum(seq,mid1,right,assist);merge(seq,left,right,mid,ReverseOrderPairNum,assist);returnReverseOrderPairNum;}intmain(){vectorintseq;for(size_t i1;i100;i){seq.push_back(i);shuffle(seq.begin(),seq.end(),default_random_engine());size_t num0;for(size_t i0;iseq.size();i){for(size_t runi1;runseq.size();run){if(seq[i]seq[run]){num;}}}vectorintassist(seq.size());size_t compute_num;vectorint_seqseq;cout逆序对数目为(compute_numgetReverseOrderPairNum(_seq,0,_seq.size()-1,assist))endl;if(numcompute_num){cout逆序对数目计算结果正确endl;}else{cout逆序对数目计算结果错误!endl;exit(-1);}}/* const int N 10; vectorint seq(N); for (size_t i 0; i seq.size(); i) { seq[i] i 1; } //reverse(seq.begin(), seq.end()); //shuffle(seq.begin(), seq.end(), default_random_engine()); size_t num 0; for (size_t i 0; i seq.size(); i) { for (size_t run i 1; run seq.size(); run) { if (seq[i] seq[run]) { num; } } } vectorint assist(N); size_t compute_num; cout 逆序对数目为 (compute_num getReverseOrderPairNum(seq, 0, seq.size() - 1, assist)) endl; if (num compute_num) { cout 逆序对数目计算结果正确 endl; } else { cout 逆序对数目计算结果错误! endl; }*/return0;}