目錄

1 問題描述

2 解決方案

2.1 蠻力法

2.2 分治法（歸并排序）

?

---

1 問題描述

給定一個(gè)隨機(jī)數(shù)數(shù)組，求取這個(gè)數(shù)組中的逆序?qū)倐€(gè)數(shù)。要求時(shí)間效率盡可能高。

?

那么，何為逆序?qū)?#xff1f;

引用自百度百科：

設(shè) A 為一個(gè)有 n 個(gè)數(shù)字的有序集?(n>1)，其中所有數(shù)字各不相同。 如果存在正整數(shù) i, j 使得 1 ≤ i < j ≤ n 而且 A[i] > A[j]，則 <A[i], A[j]> 這個(gè)有序?qū)ΨQ為 A 的一個(gè)逆序?qū)?#xff0c;也稱作逆序數(shù)。

?例如，數(shù)組（3，1，4，5，2）的逆序?qū)τ?3,1),(3,2),(4,2),(5,2)，共4個(gè)。

?

?

---

2 解決方案

2.1 蠻力法

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

即從第1個(gè)元素，開始依次和后面每一個(gè)元素進(jìn)行大小比較，若大于，則逆序?qū)€(gè)數(shù)加1。

具體代碼如下：

package com.liuzhen.systemExe;public class Main{//蠻力法求取數(shù)組A中逆序?qū)?shù)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;}//獲取一個(gè)隨機(jī)數(shù)數(shù)組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之間的隨機(jī)數(shù) }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("使用蠻力法得到結(jié)果："+result+"， 耗時(shí)："+(t2 - t1)+"毫秒");} }

運(yùn)行結(jié)果(運(yùn)行3次)：

使用蠻力法得到結(jié)果：612226389， 耗時(shí)：8094毫秒使用蠻力法得到結(jié)果：610311942， 耗時(shí)：8015毫秒使用蠻力法得到結(jié)果：610657465， 耗時(shí)：8079毫秒

?

2.2 分治法（歸并排序）?

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

具體代碼如下：

package com.liuzhen.systemExe;public class Main{public long count = 0; //全局變量，使用合并排序，計(jì)算逆序?qū)?shù)//使用歸并排序方法計(jì)算數(shù)組A中的逆序?qū)?shù)public void getReverseCount(int[] A) {if(A.length > 1) {int[] leftA = getHalfArray(A, 0); //數(shù)組A的左半邊元素int[] rightA = getHalfArray(A, 1); //數(shù)組A的右半邊元素 getReverseCount(leftA);getReverseCount(rightA);mergeArray(A, leftA, rightA);}}//根據(jù)judge值判斷，獲取數(shù)組A的左半邊元素或者右半邊元素public int[] getHalfArray(int[] A, int judge) {int[] result;if(judge == 0) { //返回?cái)?shù)組A的左半邊result = new int[A.length / 2];for(int i = 0;i < A.length / 2;i++)result[i] = A[i];} else { //返回?cái)?shù)組的右半邊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;}//合并數(shù)組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個(gè)元素均大于rightA[j]count += (lenL - i); //合并之前，leftA中元素是非降序排列，rightA中元素也是非降序排列。所以，此時(shí)就新增lenL -　i個(gè)逆序?qū)?/span>} else {A[len++] = leftA[i++];}}while(i < lenL)A[len++] = leftA[i++];while(j < lenR)A[len++] = rightA[j++];}//獲取一個(gè)隨機(jī)數(shù)數(shù)組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之間的隨機(jī)數(shù) }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("分治法得到結(jié)果："+test.count+"， 耗時(shí)："+(t2 - t1)+"毫秒");} }

運(yùn)行結(jié)果（運(yùn)行3次）：

分治法得到結(jié)果：612226489， 耗時(shí)：36毫秒分治法得到結(jié)果：610481152， 耗時(shí)：35毫秒分治法得到結(jié)果：612161208， 耗時(shí)：32毫秒

?

?

?

參考資料：

? ? ? 1.?歸并排序求逆序?qū)?/span>

總結(jié)

以上是生活随笔為你收集整理的算法笔记_065:分治法求逆序对（Java）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。