[Java] java面试题之数组中的逆序对

static int count = 0; 
 
// 将有二个有序数列a[first...mid]和a[mid...last]合并。 
static void mergearray(int a[], int first, int mid, int last, int temp[]) { 
int i = first, j = mid + 1; 
int m = mid, n = last; 
int k = 0; 
while (i <= m && j <= n) { 
 if (a[i] > a[j]) { 
 // 左数组比右数组大 
 temp[k++] = a[j++]; 
 // 因为如果a[i]此时比右数组的当前元素a[j]大， 
 // 那么左数组中a[i]后面的元素就都比a[j]大 
 // 【因为数组此时是有序数组】 
 count += mid - i + 1; 
 } else { 
 temp[k++] = a[i++]; 
 } 
} 
while (i <= m) { 
 temp[k++] = a[i++]; 
} 
while (j <= n) { 
 temp[k++] = a[j++]; 
} 
for (i = 0; i < k; i++) 
 a[first + i] = temp[i]; 
} 
 
static void mergesort(int a[], int first, int last, int temp[]) { 
if (first < last) { 
 int mid = (first + last) / 2; 
 mergesort(a, first, mid, temp); // 左边有序 
 mergesort(a, mid + 1, last, temp); // 右边有序 
 mergearray(a, first, mid, last, temp); // 再将二个有序数列合并 
} 
} 
 
static void mergesort(int a[]) { 
int[] p = new int[a.length]; 
mergesort(a, 0, a.length - 1, p); 
}