归并排序(求逆序对)

#include<stdio.h>

const int MX = 1e3 + 5;

int T[MX];

void _sort(int A[], int l, int r) {     //排序的区间为l至r;
    if(l == r)
        return ;        //如果l==r，意思是只有一个数，无需排序；
    int m = (l + r) / 2;    //将所需排序的序列分为左右两部分；
    _sort(A, l, m); _sort(A, m + 1, r);   //递归，左右两部分同理排序；

    int p1 = l, p2 = m + 1, pt = l;     //一次排序算法;
    while(p1 <= m && p2 <= r) {
        if(A[p1] < A[p2]) T[pt++] = A[p1++]; //T[]数组为临时储存数据数组
        else T[pt++] = A[p2++]
    }//此while为两边都还有数的情况下；下面两while为某一边的数已经排完
    while(p1 <= m)T[pt++] = A[p1++];
    while(p2 <= r)T[pt++] = A[p2++];
    for(int i = l; i <= r; i++)A[i] = T[i];
}
/*
如  1，3，9，7，2，6
先按递归左右排序分为     1，3，9    2，7，8
    1<2         所以第一个数为 1
    3>2         所以第二个数为 2
    3<7                        3
    9>7                        7
    9>8                        8
    剩下一个数 9               9
*/

 

归并排序求 序列的逆序对

long long ans = 0;
void guibing_sort(int l, int r) {
    if(l == r) return ;
    int mid = (l + r) / 2;
    
    guibing_sort(l, mid);
    guibing_sort(mid + 1, r);
    
    int l1 = l, r1 = mid + 1, pb = l;
    
    while(l1 <= mid && r1 <= r)
        if(a[l1] <= a[r1])
            b[pb++] = a[l1++];
        else { 
            b[pb++] = a[r1++];
            ans += (mid - l1 + 1);
        }
        
    while(l1 <= mid) b[pb++] = a[l1++];
    while(r1 <= r) b[pb++] = a[r1++];
    
    for(int i = l; i <= r; i++) a[i] = b[i];
}