题目
给定一个长度为n的整数数列，请你计算数列中的逆序对的数量。
逆序对的定义如下：对于数列的第 i 个和第 j 个元素，如果满足 i < j 且 a[i] > a[j]，则其为一个逆序对；否则不是。
输入格式 第一行包含整数n，表示数列的长度。
第二行包含 n 个整数，表示整个数列。
输出格式 输出一个整数，表示逆序对的个数。
数据范围 1≤n≤100000 输入样例： 6 2 3 4 5 6 1 输出样例： 5
算法思路
按照归并的思路，将数组分为俩个部分：arr[l,mid] arr[mid+1,r] 且俩部分各自有序的情况下 逆序对分为三种状态：1，俩个数在左侧；2，俩个数在右侧；3，大的数在左侧，小的数在右侧。
假设归并已经求出来一二俩种情况的逆序对个数为merge(l,mid)+merge(mid+1,r)个。而我们只需要考虑第三种状态的求法。
在左右部分同时各自有序的情况下：如果右部分的当前数小于左部分的第i个数，那么这个右部分的当前数会依旧大于左部分的第i+1，i+2，i+3…mid个数。这些数一共有mid-i+1个！！！！
代码
package No1
;
import java
.io
.BufferedReader
;
import java
.io
.IOException
;
import java
.io
.InputStreamReader
;
import java
.io
.OutputStreamWriter
;
import java
.io
.PrintWriter
;
import java
.io
.StreamTokenizer
;
public class Main {
public static void main(String
[] args
) throws IOException
{
StreamTokenizer in
= new StreamTokenizer(new BufferedReader(
new InputStreamReader(System
.in
)));
PrintWriter out
= new PrintWriter(new OutputStreamWriter(System
.out
));
in
.nextToken();
int n
= (int) in
.nval
;
int arr
[] = new int[n
];
int temp
[] = new int[n
];
for (int i
= 0; i
< n
; i
++) {
in
.nextToken();
arr
[i
] = (int) in
.nval
;
}
System
.out
.println(merge_sort(arr
, temp
, 0, n
- 1));
}
public static long merge_sort(int arr
[], int temp
[], int l
, int r
) {
if (l
>= r
)
return 0;
int mid
= (l
+ r
) / 2;
long res
= merge_sort(arr
, temp
, l
, mid
)
+ merge_sort(arr
, temp
, mid
+ 1, r
);
int k
= 0, i
= l
, j
= mid
+ 1;
while (i
<= mid
&& j
<= r
) {
if (arr
[i
] <= arr
[j
])
temp
[k
++] = arr
[i
++];
else {
temp
[k
++] = arr
[j
++];
res
+= mid
- i
+ 1;
}
}
while (i
<= mid
)
temp
[k
++] = arr
[i
++];
while (j
<= r
)
temp
[k
++] = arr
[j
++];
for (i
= 0, j
= l
; j
<= r
; j
++, i
++) {
arr
[j
] = temp
[i
];
}
return res
;
}
}
