归并排序求逆序对

给定数组 如{5,8,3,1}   则有<5,3><5,1><8,3><8,1><3,1> 5个逆序对 

给定数组 求其逆序对的个数

思路：归并排序   O(NlogN) 时间复杂度   O(N) 空间复杂度

代码:

int num = 0;        //逆序对个数
void mergg(int ar[],int low,int mid,int high)
{
int* b = new int[high + 1];           //b[] 复制 ar[]
for (int i = low;i <= high;++i)
    {
        b[i] = ar[i];
    }
int i = low,j = mid + 1,k = low;
while (i <= mid&&j <= high)
    {
if (b[i] <= b[j])
        {
            ar[k++] = b[i++];
        }
else
        {
            ar[k++] = b[j++];
            num += mid - i + 1;       //发生逆序，此时由于
//a[i..m]是已经有序了，那么a[i+1], a[i+2], ... a[m]都是大于a[j]的，
//都可以和a[j]组成逆序对，因此number += m - i + 1
        }
    }
while (i <= mid){ ar[k++] = b[i++]; }     //这两种情况只会发生一种
while (j <= high){ ar[k++] = b[j++]; }    //
    delete []b;
}
void merge_sort(int ar[],int low,int high)  //二路归并排序
{
if (low < high)
    {
int mid = low + (high - low)/2;
        merge_sort(ar,low,mid);
        merge_sort(ar,mid + 1,high);
        mergg(ar,low,mid,high);
    }
}

PS：  还是基础最重要 掌握扎实的基础才是王道