求数组中的逆序对

求一个N个元素的任何排序中逆序对数量（算法时间复杂度nlogn）

其实就是修改了一个归并排序的算法

#include
#include


int total = 0;  //设置一个全局变量用来统计逆序对个数
void divide(int list[], int tmp[], int start, int end)
{
    int middle = (start+end)/2;
    if(start     {
        divide(list, tmp, start, middle);
        divide(list, tmp, middle+1, end);
        merge(list, tmp, start, middle, end);
    }
}
void merge(int list[], int tmp[], int start, int middle, int end)
{
    int i = start, j = middle+1, k = start;
    while(i<=middle&&j<=end)
    {
        if(list[i]>list[j])
        {
        //把这个大括号内的代码删除就是归并排序
            int m = j;
            while(m<=end)
            {
                printf("%d, %d\n",list[i], list[m]);
                ++total;
                ++m;
            }
            tmp[k++] = list[i++];


        }else
        {
            tmp[k++] = list[j];
            ++j;
        }
    }
    while(i<=middle)
    {
        tmp[k++] = list[i++];
    }
    while(j<=end)
    {
        tmp[k++] = list[j++];
    }
    for(i=start; i<=end; i++)
    {
        list[i] = tmp[i];
    }
}


int main()
{
    int list[] = {4,3,1,2};
    int tmp[4];
    divide(list, tmp, 0, 3);
    int i, n=3;
    for(i=0; i<=n; i++)
    {
        printf("%d", list[i]);


    }
    printf("\n");
    return 0;
}