归并排序模板（附求逆序对）

逆序对满足两个条件， i < j 和 ai > aj

归并可以求逆序对， 因为是按顺序加入， 所以右区间加入的时候， 左区间的数满足 i < j， 然后左边还没有加入的数肯定比当前的a[q]要大， 应该是按大小加入的， 所以满足ai >ａｊ，　所以这个时候计数器可以加上左区间还没加入数的个数，　即ｍ－ｐ，　注意是左闭右开区间，　所以ｍ－ｐ不用加一。

 

#include<cstdio> #define REP(i, a, b) for(int i = (a); i < (b); i++) using namespace std;const int MAXN = 112; int a[MAXN], cnt, n;void merge_sort(int l, int r) //这里是左闭右开区间， 区间分两段不需要加一减一 {if(l + 1 >= r) return;int m = (l + r) >> 1; // l与r的平均数 merge_sort(l, m); merge_sort(m, r); //先递归， 再求解 int i = l, j = m, t[MAXN];REP(k, l, r){if(j >= r || i < m && a[i] <= a[j]) t[k] = a[i++]; //右区间空或者左区间非空且a[p]更优的时候加入 else t[k] = a[j++], cnt += m - i;}REP(i, l, r) a[i] = t[i]; }int main() {scanf("%d", &n);REP(i, 0, n) scanf("%d", &a[i]);merge_sort(0, n);REP(i, 0, n) printf("%d ", a[i]);printf("\n%d\n", cnt);return 0; }

 

转载于:https://www.cnblogs.com/sugewud/p/9819603.html

总结

以上是生活随笔为你收集整理的归并排序模板（附求逆序对）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。