逆序数3P的解法

1.暴力搜索 //空间复杂度n^3

#include <stdio.h>
int fun(int *base,int x,int y);

int main(void)
{
    int A[]={8,10,6,5,1,9,12};
    printf("%d",fun(A,0,6));
    return 0;
}

int fun(int *base,int x,int y)  //插入排序修改 冒泡排序类似 元素交换次数即为所求
{
    int num=0;
    for(int i=x+2;i<=y;i++)
    {
        for(int j=i-1;j>=1;j--)
        {
            if(base[j]>base[i])
            {
                for(int k=j-1;k>=0;k--)
                {
                    if(base[k]>base[j])
                        num++;
                }
            }
        }
    }
    return num;
}

2.暴力搜索2（树状数组优化） //空间复杂度(nlgn+n^2) 不确定 mark

#include <stdio.h>

int lowbit(int x) //定义一个Lowbit函数，返回参数转为二进制后,最后一个1的位置所代表的数值.
{
    return x&(-x);
}

void insert(int i,int x,int *c)
{
    while(i<=10)  //维护c数组
    {
        c[i]+=x;
        i+=lowbit(i);
    }
}

int getsum(int i,int *c) //比A[i]小的数
{
    int sum=0;
    while(i>0)
    {
        sum+=c[i];
        i-=lowbit(i);
    } 
    return sum;
}

int main(void)
{
    int A[11]={0,10,9,8,7,6,5,4,3,2,1};//A[0]位置没用
    int c[100]={0};
    int y[11]={0};
    int res=0; 
    int num=0;
    for(int i=1;i<=10;i++)
    {
        insert(A[i],1,c);
        y[i]=i-getsum(A[i],c);

    }
    for(int j=1;j<=10;j++)
    {
        num=0;
        for(int k=j;k<=10;k++)
        {
            if(A[k]<A[j])
                num++;
        }
        res+=y[j]*num;
    }
    printf("%d",res);
    return 0;
}

3.树形数组
对一个树状数组外面再用另一个树状数组记录第一个树状数组的前缀和.时间复杂度O(k⋅nlogn)
我这里重复使用了树形数组c,没有使用两个
#include

int lowbit(int x) //定义一个Lowbit函数，返回参数转为二进制后,最后一个1的位置所代表的数值.
{
    return x&(-x);
}

void insert(int i,int x,int *c) //i 位置 x数值
{
    while(i<=10)  //维护c数组
    {
        c[i]+=x;
        i+=lowbit(i);
    }
}

int getsum(int i,int *c) //比i小的数
{
    int sum=0;
    while(i>0)
    {
        sum+=c[i];
        i-=lowbit(i);
    } 
    return sum;
}

int main(void)
{
    int A[11]={0,10,9,8,7,6,5,4,3,2,1};//A[0]位置没用
    int c[100]={0};
    int d[100]={0};
    int res=0; 
    for(int i=1;i<=10;i++)
    {
        insert(A[i],1,c);
        d[i]=i-getsum(A[i],c);
    }
    for(int i=0;i<100;i++)
        c[i]=0;
    int tmp=0;
    for(int i=1;i<=10;i++)
    {
        res+=tmp-getsum(A[i],c);
        insert(A[i],d[i],c);
        tmp+=d[i];
    }

     printf("%d",res);
    return 0;
}

Note:

先按2p来，用一个数组c把每个数前面 比它大的数 的数目记录下来
例:
Input:A[6]={10,9,8,7,6,5,4}
则数组c[6]={0,1,2,3,4,5,6}
然后将数组c中数据逐个插入树形数组d
例：
0插入d[10]
1插入d[9]
c[i]插入到d数组的A[i]位置（数组A中存在0或负数的时候有问题...），插入的同时，计算此时比这个数大的个数，累加起来就是所求