java - 我无法在合并排序中使用 java 获得反转次数

Question

我正在设计 A[0..n − 1]是 n 个实数的数组。

一对 (A[i], A[j ]) 如果这些数字是乱序的，即 i < j 但 A[i]>A[j] . O(n log n)计算反转次数的算法。

我正在尝试获取反转次数，但我不知道我的代码有什么问题，我认为排序方法有问题。

    class Q2
    { 
// Merges two subarrays of arr[]. 
// First subarray is arr[l..m] 
// Second subarray is arr[m+1..r] 
         static int merge(int arr[], int l, int m, int r) 
    { 
    // Find sizes of two subarrays to be merged 
    int n1 = m - l + 1; 
    int n2 = r - m; 
    int counter =0;

    /* Create temp arrays */
    int L[] = new int [n1]; 
    int R[] = new int [n2]; 

    /*Copy data to temp arrays*/
    for (int i=0; i<n1; ++i) 
        L[i] = arr[l + i]; 
    for (int j=0; j<n2; ++j) 
        R[j] = arr[m + 1+ j]; 


    /* Merge the temp arrays */

    // Initial indexes of first and second subarrays 
    int i = 0, j = 0; 

    // Initial index of merged subarry array 
    int k = l; 
    while (i < n1 && j < n2) 
    { 
        if (L[i] <= R[j]) 
        { 
            arr[k] = L[i]; 

            i++; 
        } 
        else
        { 
            arr[k] = R[j]; 
            j++; 
            counter = counter + (m - i); 
        } 
        k++; 

    } 

    /* Copy remaining elements of L[] if any */
    while (i < n1) 
    { 
        arr[k] = L[i]; 
        i++; 
        k++; 
    } 

    /* Copy remaining elements of R[] if any */
    while (j < n2) 
    { 
        arr[k] = R[j]; 
        j++; 
        k++; 
    } 
    return counter ;
    } 

// Main function that sorts arr[l..r] using 
// merge() 
    static int sort(int arr[], int l, int r) 
   { 
    int counter=0;
    if (l < r) 
    { 
        // Find the middle point 
        int m = (l+r)/2; 

        // count first and second halves
      counter=sort(arr, l, m); 
       counter+=sort(arr , m+1, r); 

        // count two halves
       counter+= merge(arr, l, m, r); 
    } 
    return counter;
    } 



// Driver method 
     public static void main(String args[]) 
    { 
    int arr[] = {2, 4, 1, 3,5}; 





    System.out.println("Number of inversions are " + sort(arr, 0,arr.length-1 ) ); 

      } 
      }

Answer 1

您的方法存在一个根本性缺陷。

counter = counter + (m - i)

假设m之前的所有元素都小于R中的值，这是不正确的。请记住，m 之前的大部分数组可能已经排序。

counter = counter + (m - l - i)

可能更正确，但在那种情况下您可能仍在计算双倍。请注意，当它们不在原始数组中的原始位置时，您会计算它们。