使用合并排序的反转计数:为什么必须在合并子例程中将临时数组复制回原始数组

Question

我在网上看了一段使用merge排序进行反转计数的代码。代码中的merge子例程以两个数组为参数，包括需要计算反转的原始数组arr[]和用于排序的临时数组。但merge部分实际返回的唯一内容是两个数组之间的反转次数(它不返回数组(。子程序末尾有一个for循环，它将temp数组的所有值复制回数组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 && 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));
}
}

我感到困惑的代码在评论下方的底部。非常感谢你的帮助。

Answer 1

有两种方法可以处理，但在任何情况下都需要一些额外的空间。

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 && 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; 
}