逆序数的四种解法

出一个小题目：求数组的逆序数

即求数组有多少个 使得a在b前面，但是 a>b

例子：
[1 3 2] 的逆序数是1（即 <3,2> 一个)
[3 2 1] 的逆序数是3（即 <3,2> <2,1> <3,1> 三个)

3P版：
求数组有多少个 使得a在b前面，b在c前面，但是 a>b>c

1.暴力解法

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

int main(void)
{
    int A[]={8,7,6,5,10};
    printf("%d",fun_1(A,0,4));
    return 0;
}

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

2.归并排序

运用分冶法的思想

#include <stdio.h>

void merge(int *base,int x,int mid,int y,int *tmp);
void msort(int *base,int x,int y,int *tmp);
int num=0;
int main(void)
{
    int A[10]={10,9,8,7,6,5,4,3,2,1};
    int tmp[10];
    msort(A,0,9,tmp);
    printf("%d",num);
    return 0;
}

void msort(int *base,int x,int y,int *tmp)
{
    if(x<y)
    {
        int mid=x+(y-x)/2;
        msort(base,x,mid,tmp);
        msort(base,mid+1,y,tmp);
        merge(base,x,mid,y,tmp);
    }
}

void merge(int *base,int first,int mid,int last,int *temp)
{
    int i=first;
    int j=mid+1;
    int k=0;
    while(i<=mid&&j<=last)
    {
        if(base[i]<base[j])
            temp[k++]=base[i++];
        else
        {
            temp[k++]=base[j++];
            num=num+mid-i+1;
        }
    }
    while(i<=mid)
        temp[k++]=base[i++];
    while(j<=last)
        temp[k++]=base[j++];
    for(int v = 0; v < k; v++)
        base[first + v] = temp[v];
}

3.运用树状数组

#include <stdio.h>

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

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

int getsum(int i,int *c)
{
    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 res=0; 
    for(int i=1;i<=10;i++)
    {
        insert(A[i],1,c);
        res+=i-getsum(A[i],c);
    }
    printf("%d",res);
    return 0;
}

4.构建特殊二叉搜索树

#include <stdio.h>
#include <stdlib.h>
typedef struct trnode
{
    int data;
    int size; //子节点数量
    struct trnode *parent; //父节点
    struct trnode *left;
    struct trnode *right;
} Trnode;


Trnode* insert(int data,Trnode *head);
Trnode* MakeNode(int data);
void AddNode(Trnode*q,Trnode *head);

int main(void)
{
    int A[10]={10,9,8,7,6,5,4,3,2,1};
    int sum=0,num=0;
    Trnode *head=NULL;
    head=insert(A[0],head);
    for(int i=1;i<10;i++)
    {
        Trnode *target=insert(A[i],head);
        num=0;
        Trnode *p=target;
        while(p->parent!=NULL)
        {
            if(p->parent->right==p)
                num+=p->parent->size-p->size;
        }
        p=p->parent;
    }
        sum+=head->size-num;
    }
    printf("%d",sum);

    return 0;
}

Trnode* MakeNode(int data)
{
    Trnode* node=(Trnode*)malloc(sizeof(Trnode));
    node->data=data;
    node->parent=NULL;
    node->size=0;
    node->left=NULL;
    node->right=NULL;
    return node;
}

Trnode *insert(int data,Trnode *head)
{
    if(head==NULL)
    {
        return MakeNode(data);
    }
    else
    {
        Trnode*q=MakeNode(data);
        Trnode *p=head;
        AddNode(q,p);
        return q;
    }
}

void AddNode(Trnode*q,Trnode *head)
{
        if(q->data<head->data&&head->left!=NULL)
        {
            head->size++;
            head->left->parent=head;
            head=head->left;
            AddNode(q,head);
        }
        else if(q->data>head->data&&head->right!=NULL)
        {
            head->size++;
            head->right->parent=head;
            head=head->right;
            AddNode(q,head);
        }
        if(head->left==NULL&&q->data<head->data)
        {
            q->parent=head;
            head->size++;
            head->left=q;
            return;
        }
        else if(head->right==NULL&&q->data>head->data)
        {
            q->parent=head;
            head->size++;
            head->right=q;
            return;
        }
}

Note:
树状数组：
http://www.cnblogs.com/ECJTUACM-873284962/p/6380245.html
http://www.cnblogs.com/hsd-/p/6139376.html
https://zh.wikipedia.org/wiki/%E6%A0%91%E7%8A%B6%E6%95%B0%E7%BB%84
http://www.hawstein.com/posts/binary-indexed-trees.html
http://poj.org/summerschool/1_interval_tree.pdf