用 Java 計算數組中的反轉次數
1. 概述
在本教程中，我們將探討計算數組中反轉的問題，這是計算機科學中用於衡量數組距離排序有多遠的概念。
我們將首先定義反轉並提供範例來說明該概念。從這裡開始，我們將深入探討解決問題的兩種主要方法。
首先，我們將實作一個強力方法，該方法檢查每個可能的元素對以查找反轉。然後，我們將轉向更有效的分而治之技術，該技術利用修改後的合併排序演算法來顯著減少比較次數。
2. 什麼是數組中的反轉？
數組中的反轉只是兩個元素亂序的情況。具體來說，如果較低索引處的元素大於較高索引處的元素，則會發生反轉。換句話說，如果我們有一個陣列A ，則反轉是任一對索引(i, j)其中：
-
i < j -
A[i] > A[j]
在排序數組中，我們沒有反轉，因為每個元素都被正確放置。但在未排序的陣列中，反轉的次數告訴我們陣列的「無序」程度。反轉次數越多，我們需要採取的步驟就越多，透過交換相鄰元素來對陣列進行排序。
2.1.例子
讓我們來看一個簡單的例子。假設我們有一個陣列：
int[] array = {3, 1, 2};在這個數組中，有兩個反轉：
-
(3, 1)因為3出現在1之前且3 > 1 -
(3, 2)因為3出現在2之前且3 > 2
3. 蠻力方法
計算反轉的蠻力方法很簡單。我們遍歷數組中每對可能的元素並檢查它們是否形成反轉。這種方法很容易理解和實現，但時間複雜度為O(n^2) ，這使得它對於較大的數組效率低下。
在這種方法中，我們使用巢狀循環迭代數組中的每個元素。對於每對(i, j) ，其中i < j ，我們檢查是否A[i] > A[j] 。如果是，我們就發現了反轉並增加了計數：
@Test
void givenArray_whenCountingInversions_thenReturnCorrectCount() {
int[] input = {3, 1, 2};
int expectedInversions = 2;
int actualInversions = countInversionsBruteForce(input);
assertEquals(expectedInversions, actualInversions);
}
int countInversionsBruteForce(int[] array) {
int inversionCount = 0;
for (int i = 0; i < array.length - 1; i++) {
for (int j = i + 1; j < array.length; j++) {
if (array[i] > array[j]) {
inversionCount++;
}
}
}
return inversionCount;
}這種強力解決方案對於小型陣列效果很好，但隨著陣列規模的增加，其效率低下的情況就變得明顯。
4. 最佳化方法：分而治之
分而治之的方法透過利用合併排序的原理，顯著提高了計算反轉的效率。我們不是單獨檢查每一對，而是遞歸地將數組分成兩半，直到每一半都有一個元素（或沒有元素）。當我們按排序順序將這些半部合併在一起時，我們會計算左半部中的元素大於右半部中的元素的反轉：
@Test
void givenArray_whenCountingInversionsWithOptimizedMethod_thenReturnCorrectCount() {
int[] inputArray = {3, 1, 2};
int expectedInversions = 2;
int actualInversions = countInversionsDivideAndConquer(inputArray);
assertEquals(expectedInversions, actualInversions);
}接下來，我們定義countInversionsDivideAndConquer()方法。該方法作為演算法的入口點。它檢查輸入數組是否有效並將反轉計數邏輯委託給另一個方法：
int countInversionsDivideAndConquer(int[] array) {
if (array == null || array.length <= 1) {
return 0;
}
return mergeSortAndCount(array, 0, array.length - 1);
}此演算法的核心邏輯位於mergeSortAndCount()方法中。此方法將數組分為兩半，遞歸處理每一半以計算其中的反轉，然後按排序順序將它們合併在一起，同時計算兩半之間發生的任何反轉：
int mergeSortAndCount(int[] array, int left, int right) {
if (left >= right) {
return 0;
}
int mid = left + (right - left) / 2;
int inversions = mergeSortAndCount(array, left, mid) + mergeSortAndCount(array, mid + 1, right);
inversions += mergeAndCount(array, left, mid, right);
return inversions;
}最後， mergeAndCount()方法處理合併過程。它合併數組的兩個已排序的一半，並同時計算交叉反轉（當左半部的元素大於右半部的元素時）。
mergeAndCount()方法的第一部分建立臨時陣列來儲存要合併的陣列的左半部和右半部：
int[] leftArray = new int[mid - left + 1];
int[] rightArray = new int[right - mid];
System.arraycopy(array, left, leftArray, 0, mid - left + 1);
System.arraycopy(array, mid + 1, rightArray, 0, right - mid);System.arraycopy()有效地將元素從原始陣列複製到臨時陣列中。
建立臨時數組後，我們初始化用於遍歷的指標和一個變數來追蹤反轉。在下一部分中，我們在計算交叉反轉的同時合併兩半：
int i = 0, j = 0, k = left, inversions = 0;
while (i < leftArray.length && j < rightArray.length) {
if (leftArray[i] <= rightArray[j]) {
array[k++] = leftArray[i++];
} else {
array[k++] = rightArray[j++];
inversions += leftArray.length - i;
}
}我們將leftArray.length – i加入inversions計數器，因為這些都是導致反轉的元素。
處理完一個數組中的所有元素後，另一個數組中可能仍然剩餘元素。這些元素被複製到原始數組中：
while (i < leftArray.length) {
array[k++] = leftArray[i++];
}
while (j < rightArray.length) {
array[k++] = rightArray[j++];
}
return inversions;這種最佳化使演算法能夠實現改進的O(n * log n)時間複雜度。
5. 比較
在比較暴力法和分而治之方法時，主要差異在於它們的效率。暴力方法會迭代數組中所有可能的對，檢查每個對的反轉，這會導致時間複雜度為O(n^2) 。這使得大型數組效率低下，因為操作數量隨著數組大小的增加而快速增長。
相較之下，分而治之方法利用合併排序演算法在對陣列進行排序時有效地計算反轉次數。透過將數組分成兩半併計算這些兩半內和兩半之間的反轉，該方法實現了O(n * log n)的時間複雜度。這項重大改進使其更適合更大的資料集，因為它可以隨著輸入大小的增加而有效地擴展。
六、結論
在本文中，我們探討如何計算數組中的反轉次數。我們從一個清晰的定義和一個實際的例子開始來解釋反轉。然後，我們研究了兩種解決該問題的方法。第一種是簡單的暴力方法。第二種是使用合併排序的更有效的分而治之方法。暴力法很容易實現，但對於大型陣列來說效率較低。相較之下，分而治之的方法使用遞歸來大幅降低時間複雜度。
與往常一樣，原始碼可以在 GitHub 上取得。