求逆序對問題用歸并排序的時間復雜度比暴力算法更低。

假設有一個數組{8，1，2，5，7，4，3，6}

首先歸并排序第一次對數組進行分割? ? ? 8 1 2 5? ? ? 7 4 3 6

二次分割? ? ? 8 1? ? ? 25? ? ? 74? ? ? 36

三次分割? ? ? 8? ? ? 1? ? ? 2? ? ? 5? ? ? 7? ? ? 4? ? ? 3? ? ? 6

第一次合并? ? ?18? ? ?25? ? ?74? ? ?36? ? ? reorder[1]=2, order[1]=2

//用reorder[i]來記錄第i次合并中存在的逆序對數,order[i]來記錄第i次合并中存在的順序對數。

第二次合并? ? ?1258? ? ?3467? ? ?reorder[2]=5,?order[2]=3

第三次合并? ? ?12345678? ? ?? ? ?reorder[3]=6, order[3]=10

那么數組{8，1，2，5，7，4，3，6}中存在的逆序對就等于reorder[1]+reorder[2]+reorder[3]=13

將數組{8，1，2，5，7，4，3，6}每2^2個為一組進行翻轉{5，2，1，8，6，3，4，7}

首先歸并排序第一次對數組進行分割? ? ? 5?2?1?8? ? ? 6?3?4?7

二次分割? ? ? 5?2? ? ? 18? ? ? 63? ? ? 47

三次分割? ? ? 5? ? ? 2? ? ? 1? ? ? 8? ? ? 6? ? ?3? ? ? 4? ? ? 7

第一次合并? ? ?25? ? ?18? ? 36? ? ?47? ? ? reorder[1]=2, order[1]=2

第二次合并? ? ?1258? ? ?3467? ? ?reorder[2]=3,?order[2]=5

第三次合并? ? ?12345678? ? ?? ? ?reorder[3]=6, order[3]=10

那么數組{5，2，1，8，6，3，4，7}中存在的逆序對就等于reorder[1]+reorder[2]+reorder[3]=11

由此我們可以觀察到對數組每2^2個進行翻轉時，reorder[1]和order[1]進行了互換,reorder[2]和order[2]亦是如此。

所以對數組每2^i個進行翻轉時，我們可以把1~i的reorder和order數組元素互換即可繼續通過計算reorder數組的累加和來求得數組的逆序對數。

import java.util.ArrayList;

import java.util.Scanner;

public class Main?{

public static void main(String[] args)

{

Scanner sc = new Scanner(System.in);

int n = sc.nextInt();

int N = 1 << n;

int[] a = new int[N];

int[] b = new int[N];//用來存儲數組的逆序,對逆序的數組進行一次歸并排序可以直接得到order數組

int[] order = new int[n + 1];//為了便于計算，所以設置order下標是1~n，因此數組大小為n+1

int[] reorder = new int[n + 1];

for (int i = 0; i < N; i++)

{

a[i] = sc.nextInt();

b[N - i - 1] = a[i];

}

MergeSort(a, 0, N - 1, reorder, n);//對整個數組進行歸并排序，n表示對reorder[1]~reorder[n]進行初始化

MergeSort(b, 0, N - 1, order, n);//對整個逆序數組進行歸并排序，完成對order[1]~order[n]的初始化

int m = sc.nextInt();

while(m-- > 0)

{

int count = 0;

int q = sc.nextInt();

for (int i = 1; i <= q; i++) //像之前講的，將1~q的reorder[i]和order[i]進行互換

{

int temp = reorder[i];

reorder[i] = order[i];

order[i] = temp;

}

for (int i = 1; i <= n; i++)

{

count+= reorder[i];//累加reorder數組，求得對數組中每2^q個元素進行翻轉后的逆序對數

}

System.out.println(count);

}

}

public static void MergeSort(int[] a , int left, int right, int[] reorder, int index)

{

if(left < right)

{

int mid = (right + left) / 2;

MergeSort(a, left, mid, reorder,index - 1);

MergeSort(a, mid + 1, right, reorder,index -1);

if(a[mid] > a[mid+1])//如果a[mid]<=a[mid+1]，則原數組有序，不需要合并

Merge(a, left, right,reorder, index);

}

}

public static void Merge(int[] a, int left, int right,int[] reorder, int index)//index表示對reorder[index]進行初始化

{

int mid = (right + left) / 2;

int Length1 = mid - left + 1;

int Length2 = right - mid;

int[] l = new int[Length1];//存儲a[left]~a[mid]

int[] r = new int[Length2];//存儲a[mid+1]~a[right]

System.arraycopy(a, left, l, 0, Length1);//對l進行初始化

System.arraycopy(a, mid + 1, r, 0, Length2);//對r進行初始化

int i = 0;

int j = 0;

int c= 0;

int k = left;

while(i < Length1 && j < Length2)

{

if(l[i] <= r[j])

{

a[k] = l[i];

i++;

}

else

{

a[k] = r[j];

j++;

c += Length1 - i;//當l[i]>r[j]時，因為l是遞增序列，所以l[i]~l[Length1-1]均>r[j]，所以有Length1-i個元素大于r[j]

}

k++;

}

System.arraycopy(l, i, a, k, Length1 - i);//前面歸并排序MergeSort中調用Merge合并的條件是a[mid]>a[mid+1],因為當a[mid]<=a[mid+1]時說明原數組有序，無需合并。l[Length1-1]>r[Length2-1],即l數組的最大值大于r數組的最大值，所以當r中的數全部進入a數組后，l數組中仍有剩余。

reorder[index] += c;

}

}