欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

归并排序+逆序对个数

程序员文章站 2022-05-10 11:51:29
...
void merge_sort(int* A,int x,int y,int* T)
{
    if(y - x <= 1) return;int cnt = 0;
    int m = x + (y - x) / 2;                //划分
    merge_sort(A,x,m,T);merge_sort(A,m,y,T);//分别对子问题求解
    int p = x, q = m, i = x,cnt = 0;
    while(q < m || p < y)
    {
        if(q >= y || (p < m && A[p] <= A[q])) T[i++] = A[p++];
        //左半部分较小时 或 右半部分已全部加入时,从左半数组复制到临时空间
        else
        {
            T[i++] = A[q++];//否则从右半数组复制到临时空间
            cnt += m - p;   //因为先放入的p个元素都比右边这个元素小,所以此时对右边每个元素,左边比它大的元素有m-p个
        }
    }
    for(i = x;i < y;i++)
        A[i] = T[i];//从临时空间复制回A数组
}