算法筆記_065:分治法求逆序對（Java）

目錄

1 問題描述

2 解決方案

2.1 蠻力法

2.2 分治法（歸并排序）

?

---

1 問題描述

給定一個隨機數數組，求取這個數組中的逆序對總個數。要求時間效率盡可能高。

?

那么，何為逆序對？

引用自百度百科：

設 A 為一個有 n 個數字的有序集?(n>1)，其中所有數字各不相同。

如果存在正整數 i, j 使得 1 ≤ i < j ≤ n 而且 A[i] > A[j]，則 <A[i], A[j]> 這個有序對稱為 A 的一個逆序對，也稱作逆序數。

?例如，數組（3，1，4，5，2）的逆序對有(3,1),(3,2),(4,2),(5,2)，共4個。

?

?

---

2 解決方案

2.1 蠻力法

初步一看，使用蠻力是最直接也最簡單的方法，但是時間效率為O(n^2)。

即從第1個元素，開始依次和后面每一個元素進行大小比較，若大于，則逆序對個數加1。

具體代碼如下：

package com.liuzhen.systemExe;public class Main{//蠻力法求取數組A中逆序對數public int bruteReverseCount(int[] A) {int result = 0;for(int i = 0;i < A.length;i++) {for(int j = i;j < A.length;j++) {if(A[i] > A[j])result++;}}return result;}//獲取一個隨機數數組public int[] getRandomArray(int n) {int[] result = new int[n];for(int i = 0;i < n;i++) {result[i] = (int)( Math.random() * 50);  //生成0~50之間的隨機數
        }return result;}public static void main(String[] args){long t1 = System.currentTimeMillis();Main test = new Main();int[] A = test.getRandomArray(50000);int result = test.bruteReverseCount(A);long t2 = System.currentTimeMillis();System.out.println("使用蠻力法得到結果："+result+"， 耗時："+(t2 - t1)+"毫秒");}
}

運行結果(運行3次)：

使用蠻力法得到結果：612226389， 耗時：8094毫秒使用蠻力法得到結果：610311942， 耗時：8015毫秒使用蠻力法得到結果：610657465， 耗時：8079毫秒

?

2.2 分治法（歸并排序）?

除了蠻力法，此處可以借用歸并排序的思想來解決此題，此時時間復雜度為O（n*logn）。歸并排序，具體是先進行對半劃分，直到最后左半邊數組只有一個元素，右半邊數組中也只有一個元素時，此時開始進行回溯合并。那么，計算逆序對個數的關鍵，就在于此處的回溯合并過程，當左半邊元素（PS：回溯過程中，左半邊和右半邊元素均已是升序排序）中出現大于右半邊元素時，那么左半邊這個元素及其后面的所有元素均大于這個右半邊元素，記這些元素個數為len，那么逆序對個數要自增len。

具體代碼如下：

package com.liuzhen.systemExe;public class Main{public long count = 0;   //全局變量，使用合并排序，計算逆序對數//使用歸并排序方法計算數組A中的逆序對數public void getReverseCount(int[] A) {if(A.length > 1) {int[] leftA = getHalfArray(A, 0);   //數組A的左半邊元素int[] rightA = getHalfArray(A, 1);  //數組A的右半邊元素
            getReverseCount(leftA);getReverseCount(rightA);mergeArray(A, leftA, rightA);}}//根據judge值判斷，獲取數組A的左半邊元素或者右半邊元素public int[] getHalfArray(int[] A, int judge) {int[] result;if(judge == 0) {   //返回數組A的左半邊result = new int[A.length / 2];for(int i = 0;i < A.length / 2;i++)result[i] = A[i];} else {    //返回數組的右半邊result= new int[A.length - A.length / 2];for(int i = 0;i < A.length - A.length / 2;i++)result[i] = A[A.length / 2 + i];}return result;}//合并數組A的左半邊和右半邊元素，并按照非降序序列排列public void mergeArray(int[] A, int[] leftA, int[] rightA) {int len = 0;int i = 0;int j = 0;int lenL = leftA.length;int lenR = rightA.length;while(i < lenL && j < lenR) {if(leftA[i] > rightA[j]) {A[len++] = rightA[j++]; //將rightA[j]放在leftA[i]元素之前，那么leftA[i]之后lenL - i個元素均大于rightA[j]count += (lenL - i);   //合并之前，leftA中元素是非降序排列，rightA中元素也是非降序排列。所以，此時就新增lenL -　i個逆序對} else {A[len++] = leftA[i++];}}while(i < lenL)A[len++] = leftA[i++];while(j < lenR)A[len++] = rightA[j++];}//獲取一個隨機數數組public int[] getRandomArray(int n) {int[] result = new int[n];for(int i = 0;i < n;i++) {result[i] = (int)( Math.random() * 50);  //生成0~50之間的隨機數
        }return result;}public static void main(String[] args){long t1 = System.currentTimeMillis();Main test = new Main();int[] A = test.getRandomArray(50000);test.getReverseCount(A);long t2 = System.currentTimeMillis();System.out.println("分治法得到結果："+test.count+"， 耗時："+(t2 - t1)+"毫秒");}
}

運行結果（運行3次）：

分治法得到結果：612226489， 耗時：36毫秒分治法得到結果：610481152， 耗時：35毫秒分治法得到結果：612161208， 耗時：32毫秒

?

?

?

參考資料：

? ? ? 1.?歸并排序求逆序對