Блог

Я просматривал фрагмент кода в Интернете для подсчета инверсий с использованием сортировки слиянием. Подпрограмма слияния в коде принимает два массива в качестве параметров, включая arr[] , исходный массив, инверсии которого необходимо подсчитать, и временный массив, используемый для сортировки. Но единственное, что фактически возвращает часть слияния, — это количество инверсий между двумя массивами (оно не возвращает массив). В конце подпрограммы есть цикл for, который копирует все значения временного массива обратно в массив arr[], так что arr[] становится объединенным. Программа корректно работает только с этим циклом for , но я не понимаю, почему. Разве оба массива, переданные в качестве аргументов, не выпадают из области видимости при возврате метода? Как это влияет на изменение arr[] в самом конце подпрограммы?

   static long mergeSort(int arr[], int array_size)
    {
        int temp[] = new int[array_size];
        return _mergeSort(arr, temp, 0, array_size - 1);
    }

    static long _mergeSort(int arr[], int temp[], int left, int right)
    {
        int mid = 0;
        long inv_count = 0;
        if (right > left) {

            mid = (right   left) / 2;


            inv_count = _mergeSort(arr, temp, left, mid);
            inv_count  = _mergeSort(arr, temp, mid   1, right);

            inv_count  = merge(arr, temp, left, mid   1, right);
        }
        return inv_count;
    }

 
    static long merge(int arr[], int temp[], int left, int mid, int right)
    {
       int i = left;
       int k = left;
       int j = mid;
       long mergeInvCount = 0;

       while (i < mid amp;amp; j <= right) {
           if (arr[i] <= arr[j]) {
               temp[k  ] = arr[i  ];
           } else {
               temp[k  ] = arr[j  ];
               mergeInvCount = mergeInvCount   mid - i;
           }
       }
     while(i < mid) {
         temp[k  ] = arr[i  ];
           }
     while(j <= right) {
         temp[k  ] = arr[j  ];
       }
/* I don't get what this code is doing:*/
        for (i = left; i <= right; i  ) {
            arr[i] = temp[i];
        }
         return mergeInvCount;
    }

    
    public static void main(String[] args) throws IOException
    {
        int coolArray[] = {5, 78, 2, 34, 56, 23, 45, 2, 65, 4, 2, 4};
        System.out.println(mergeSort(coolArray, 12));
    }
}
  

Код, который меня смущает, находится внизу, под комментарием.
Большое спасибо за любую помощь.

Есть два способа справиться с этим, но в любом случае вам потребуется дополнительное пространство.

1. Либо создайте временные левый и правый подмассивы и внесите изменения в исходный массив во время сортировки, либо

2. Используемый здесь, используйте временный массив, примените к нему сортировку слиянием и скопируйте значения обратно в исходный массив. Потому что, если мы не будем копировать обратно в исходный массив (подмассив останется несортированным в исходном массиве и, следовательно, когда мы применим к нему слияние, инверсии будут отличаться от фактического количества).

Альтернативный и, возможно, менее запутанный подход заключается в следующем:

 private static int mergeAndCount(int[] arr, int l, int m, int r) 
{ 

    int[] left = Arrays.copyOfRange(arr, l, m   1); 
    int[] right = Arrays.copyOfRange(arr, m   1, r   1); 

    int i = 0, j = 0, k = l, swaps = 0; 

    while (i < left.length amp;amp; j < right.length) { 
        if (left[i] <= right[j]) 
            arr[k  ] = left[i  ]; 
        else { 
            arr[k  ] = right[j  ]; 
            swaps  = (m   1) - (l   i); 
        } 
    } 
    return swaps; 
} 

private static int mergeSortAndCount(int[] arr, int l, int r) 
{ 
    int count = 0; 

    if (l < r) { 
        int m = (l   r) / 2; 

        count  = mergeSortAndCount(arr, l, m); 

        count  = mergeSortAndCount(arr, m   1, r); 

        count  = mergeAndCount(arr, l, m, r); 
    } 

    return count; 
}