Я не могу получить количество инверсий, используя Java в сортировке слиянием

Question

Я создаю A[0..n − 1] массив из n действительных чисел.

Пара (A [i], A [j]) называется инверсией, если эти числане в порядке, то есть 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)

на

 counter = counter + (n1 - i)

Иллюстрация: Предположим, левый массив L с номерами 1, 6, 8, 9 и правый массив R с номерами 4, 5, 7. Ниже показаны итерации цикла для одного шага рекурсии:

Как правило, вы можете отсортировать массив, выполнив инверсиив другом порядке.Тем не менее, минимальное количество инверсий, необходимых для сортировки, является однозначным и, следовательно, не зависит от этого порядка.Поскольку алгоритм использует одну из этих альтернативных последовательностей, он обеспечивает однозначное минимальное количество инверсий.В частности, это означает, что инверсия не учитывается дважды или не учитывается.

Алгоритм предусматривает для вашего массива {2, 4, 1, 3, 5} минимальное количество из 3 инверсий в общей сложности: (4, 1),(4, 3) и (2,1).

Answer 2

В вашем методе есть один фундаментальный недостаток.

counter = counter + (m - i)

предполагает, что все элементы до m меньше значения в R, что неверно.Помните, что большая часть массива до m уже может быть отсортирована.

counter = counter + (m - l - i)

может быть более правильным, но вы, вероятно, все еще считаете в этом случае двойной.Обратите внимание, что вы считаете их, когда они не находятся в исходном месте в исходном массиве.