題目來源：https://www.acwing.com/problem/content/790/
題目描述
給定一個長度為 n 的整數數列，請你計算數列中的逆序對的數量，
逆序對的定義如下：對于數列的第 i 個和第 j個元素，如果滿足 i<j且 a[i]>a[j]，則其為一個逆序對；否則不是，
輸入格式
第一行包含整數 n，表示數列的長度，
第二行包含 n個整數，表示整個數列，
輸出格式
輸出一個整數，表示逆序對的個數，
資料范圍
1≤n≤100000 數列中的元素的取值范圍 1～10^9
輸入樣例：
6
2 3 4 5 6 1
輸出樣例：
5
思路講解
-
首先還是理解下題意吧，通俗點講，逆序對就是指，一個陣列中的兩個數，如果前面的數大于后面的那個數，那么這兩個數就組成一個逆序對
-
求逆序對的演算法是利用了分治的思想,在分治的程序中會將序列分為兩部分，此時逆序對可以分為三種情況：兩個數都在左邊的（設為s1），兩個數都在右邊的（s2），一個數在左邊一個數在右邊的(s3)，現在假設我們在歸并排序的時候寫的函式merge_sort(int[] q, int left, int right)可以回傳l到r區間中逆序對數量，那么s1便是左半邊的回傳值，s2則是右半邊的回傳值，而s3卻無法如此得到，因為s3不知道跨度是什么，那么核心問題就在于怎么求s3，以及怎么使我們的merge_sort(int[] arr, int l, int r)可以回傳l到r區間中逆序對數量，
-
我們應當確定的是，再歸并排序中，其下等待歸并的所有小陣列，結尾有序陣列，也就是說，若a陣列中的a1大于b陣列中的b1，那么a2，a3······都會是大于b1的，那么我們就會很自然的得到res(最終結果)=mid-i+1，
-
而我們是如何得到情況s1和s2的呢？很顯然的是，在遞回程序中，s1與s2其實是處于s3的狀態的，因此很輕易的就可以得到上述結論
-
需要強調的幾點是
-
即使我們是求逆序對數量，也應當在排序后進行“掃尾”作業，以確保后續遞回的正常進行
-
由于我們求的是逆序對，所以我們應當將方法回傳值設為long型別，因為本題資料范圍1≤n≤100000，若陣列為降序陣列，int型別無法滿足要求，應設定為long，
-
代碼
import java.util.Scanner;
?
public class Main {
//開辟足夠大的陣列空間
static int N = 100010;
static int[] q = new int[N], temp = new int[N];
public static void main(String[] args) {
//輸入陣列大小以及陣列的值
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
for (int i = 0; i < n; i++) {
q[i] = sc.nextInt();
}
?
//運行方法并輸出結果
System.out.println(merge_sort(q,0,n-1));
}
?
public static long merge_sort(int []q,int left,int right) {
//進行判斷
if (left >= right) return 0;
?
//進行遞回，將陣列分為最小單位的值,接著在從最小進行排序，逐漸到整個陣列
int mid = left + (right - left) / 2;
?
//確立回傳值
long res = merge_sort(q,left,mid) + merge_sort(q,mid+1,right);
?
int i = left, j = mid + 1;//建立雙指標，i指向前一個數，j指向后一個數
int k = 0;//令temp從0開始，往其中添加元素
?
//進行歸并操作，將數存放至臨時陣列temp
while (i <= mid && j <= right) {//確認邊界
if (q[i] <= q[j])
temp[k++] = q[i++];
else{
temp[k++] = q[j++];
res += mid - i + 1;
}
}
//防止i或j提前用光的情況發生，并保持后續陣列排列正確
while (i <= mid) temp[k++] = q[i++];
while (j <= right) temp[k++] = q[j++];
?
for(i = left, k = 0; i <=