Possible Duplicate:
Counting inversions in an array


这是我几个月前接受一家公司面试开发人员职位时遇到的编程问题。

给定一个由N个整数组成的数组A，该数组的求反定义为任意一对索引(a，b)，使得a
编写一个函数:

int inversion_count(int A[], int n); 

它计算A中的求反数，如果该数超过1,000,000,000，则返回-1。例如，在以下数组中

A[0]=-1 A[1]=6 A[2]=3 A[3]=4 A[4]=7 A[5]=4 

有四个反转:

(1,2)  (1,3)  (1,5)  (4,5) 

因此该函数应返回4。

我以一种非常常见的方式解决了这个问题:使用双循环。

int i, j; 
long count; 
for (i = 0; i < n; i++) { 
   for (j = i+1; j < n; j++) { 
      if (A[i] > A [j]) count++; 
      if (count > 1000000000) break; // exit loop 
   } 
   if (count > 1000000000) break; // exit loop 
} 
if (count > 1000000000) return -1; 
else return count; 

因此它的运行时间是:O(nsquare)，并被告知效率不高。我现在正在考虑解决该问题的另一种方法，也许使用 n log n 算法，但是我还没有弄清楚。有任何想法吗？