求数组的逆序数
概念和算法原理我就不说了，中午要吃饭，直接给代码。
int inverseNumber(int *arr, int len)
{
if (len==1)
return 0;
int inverseLeft=inverseNumber(arr, len/2);
int inverseRight=inverseNumber(arr+len/2, len-len/2);
int *sorted = new int[len];
int i=0, j=len/2, k=0,inverse=0;
while (i<len/2 && j < len)
{
if (arr[i] <= arr[j])
sorted[k++] = arr[i++];
else
{
sorted[k++] = arr[j++];
inverse += len/2 - i;
}
}
while(i<len/2)
sorted[k++] = arr[i++];
while(j<len)
sorted[k++] = arr[j++];
memcpy(arr,sorted,len*sizeof(int));
return inverse+inverseLeft+inverseRight;
}
补充：综合编程 , 其他综合 ,
