題目：在數(shù)組中的兩個數(shù)字如果前面一個數(shù)字大于后面的數(shù)字，則這兩個數(shù)字組成一個逆序對。輸入一個數(shù)組，求出這個數(shù)組中的逆序對的總數(shù)

例如在數(shù)組｛7，5，6，4｝中，一共存在5對逆序對，分別是｛7，6｝，｛7，5｝，｛7，4｝，｛6，4｝，｛5，4｝。

看到這個題目，我們的第一反應就是順序掃描整個數(shù)組。每掃描到一個數(shù)組的時候，逐個比較該數(shù)字和它后面的數(shù)字的大小。如果后面的數(shù)字比它小，則這兩個數(shù)字就組成一個逆序對。假設數(shù)組中含有n個數(shù)字。由于每個數(shù)字都要和O(n）個數(shù)字做比較，因此這個算法的時間復雜度為O(n2)。我們嘗試找找更快的算法。

我們以數(shù)組｛7，5，6，4｝為例來分析統(tǒng)計逆序對的過程，每次掃描到一個數(shù)字的時候，我們不能拿它和后面的每一個數(shù)字做比較，否則時間復雜度就是O(n2)因此我們可以考慮先比較兩個相鄰的數(shù)字。

如下圖所示，我們先把數(shù)組分解稱兩個長度為2的子數(shù)組，再把這兩個子數(shù)組分別茶城兩個長度為1的子數(shù)組。接下來一邊合并相鄰的子數(shù)組，一邊統(tǒng)計逆序對的數(shù)目。在第一對長度為1的子數(shù)組｛7｝，｛5｝中7大于5，因此｛7，5｝組成一個逆序對。同樣在第二對長度為1的子數(shù)組｛6｝，｛4｝中也有逆序對｛6，4｝。由于我們已經(jīng)統(tǒng)計了這兩隊子數(shù)組內(nèi)部逆序對，因此需要把這兩對子數(shù)組排序，以免在以后的統(tǒng)計過程中再重復統(tǒng)計。

接下來我們統(tǒng)計兩個長度為2的子數(shù)組之間的逆序對。

我們先用兩個指針分別指向兩個子數(shù)組的末尾，并每次比較兩個指針指向的數(shù)字。如果第一個子數(shù)組中的數(shù)字大于第二個子數(shù)組中的數(shù)字，則構成逆序對，并且逆序對的數(shù)目等于第二個子數(shù)組中的剩余數(shù)字的個數(shù)。如果第一個數(shù)組中的數(shù)字小于或等于第二個數(shù)組中的數(shù)字，則不構成逆序對。每一次比較的時候，我們都把較大的數(shù)字從后往前復制到一個輔助數(shù)組中去，確保輔助數(shù)組中的數(shù)字是遞增排序的。在把較大的數(shù)字復制到數(shù)組之后，把對應的指針向前移動一位，接著來進行下一輪的比較。

經(jīng)過前面詳細的討論，我們可以總結出統(tǒng)計逆序對的過程：先把數(shù)組分隔成子數(shù)組，先統(tǒng)計出子數(shù)組內(nèi)部的逆序對的數(shù)目，然后再統(tǒng)計出兩個相鄰子數(shù)組之間的逆序對的數(shù)目。在統(tǒng)計逆序對的過程中，還需要對數(shù)組進行排序。如果對排序算法很熟悉，我們不難發(fā)現(xiàn)這個排序的過程就是歸并排序。

 static int count = 0; 
 
 // 將有二個有序數(shù)列a[first...mid]和a[mid...last]合并。 
 static void mergearray(int a[], int first, int mid, int last, int temp[]) { 
 int i = first, j = mid + 1; 
 int m = mid, n = last; 
 int k = 0; 
 while (i <= m && j <= n) { 
  if (a[i] > a[j]) { 
  // 左數(shù)組比右數(shù)組大 
  temp[k++] = a[j++]; 
  // 因為如果a[i]此時比右數(shù)組的當前元素a[j]大， 
  // 那么左數(shù)組中a[i]后面的元素就都比a[j]大 
  // 【因為數(shù)組此時是有序數(shù)組】 
  count += mid - i + 1; 
  } else { 
  temp[k++] = a[i++]; 
  } 
 } 
 while (i <= m) { 
  temp[k++] = a[i++]; 
 } 
 while (j <= n) { 
  temp[k++] = a[j++]; 
 } 
 for (i = 0; i < k; i++) 
  a[first + i] = temp[i]; 
 } 
 
 static void mergesort(int a[], int first, int last, int temp[]) { 
 if (first < last) { 
  int mid = (first + last) / 2; 
  mergesort(a, first, mid, temp); // 左邊有序 
  mergesort(a, mid + 1, last, temp); // 右邊有序 
  mergearray(a, first, mid, last, temp); // 再將二個有序數(shù)列合并 
 } 
 } 
 
 static void mergeSort(int a[]) { 
 int[] p = new int[a.length]; 
 mergesort(a, 0, a.length - 1, p); 
 } 

以上就是本文的全部內(nèi)容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。

最新評論