以下是我编写的代码，目的是从文本文件中读取100000个整数并使用Merge Sort进行对它们进行排序。
问题：
-
排序的整数仅在Eclipse控制台中以正确的顺序显示，但是当我尝试将其写入输出文本文件时，订单已更改。
-
根据我的知识，从给定文本文件中的100000个整数的反转计数值应在
2407905288左右，但我得到的值是8096。
请帮助我解决这两个问题。非常感谢您。
package com.inversioncount;
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
public class inversioncount {
public static int mergeSort(Integer[] arr, int array_size) {
int temp[] = new int[array_size];
return _mergeSort(arr, temp, 0, array_size - 1);
}
/* An auxiliary recursive method that sorts the input array and
returns the number of inversions in the array. */
public static int _mergeSort(Integer arr[], int[] temp, int left, int right) {
int mid, count = 0;
if (right > left) {
/* Divide the array into two parts and call _mergeSortAndCountInv()
for each of the parts */
mid = (right + left) / 2;
/* Inversion count will be sum of inversions in left-part, right-part
and number of inversions in merging */
count = _mergeSort(arr, temp, left, mid);
count += _mergeSort(arr, temp, mid + 1, right);
/* Merge the two parts */
count += merge(arr, temp, left, mid + 1, right);
}
return count;
}
/* This method merges two sorted arrays and returns inversion count in
the arrays.*/
static int merge(Integer arr[], int temp[], int left, int mid, int right) {
int x, y, z;
int count = 0;
x = left; /* i is index for left subarray*/
y = mid; /* j is index for right subarray*/
z = left; /* k is index for resultant merged subarray*/
while ((x <= mid - 1) && (y <= right)) {
if (arr[x] <= arr[y]) {
temp[z++] = arr[x++];
} else {
temp[z++] = arr[y++];
count = count + (mid - x);
}
}
/* Copy the remaining elements of left subarray
(if there are any) to temp*/
while (x <= mid - 1)
temp[z++] = arr[x++];
/* Copy the remaining elements of right subarray
(if there are any) to temp*/
while (y <= right)
temp[z++] = arr[y++];
/* Copy back the merged elements to original array*/
for (x = left; x <= right; x++)
arr[x] = temp[x];
return count;
}
// Driver method to test the above function
public static void main(String[] args) throws FileNotFoundException {
try {
BufferedReader br = new BufferedReader(new FileReader("IntegerArray.txt"));
List<Integer> lines = new ArrayList<Integer>();
String line;
while ((line = br.readLine()) != null) {
lines.add(Integer.parseInt(line));
}
br.close();
Integer[] inputArray = lines.toArray(new Integer[lines.size()]);
inversioncount.mergeSort(inputArray, inputArray.length - 1);
System.out.println("Number of inversions are " + mergeSort(inputArray, inputArray.length));
//BufferedWriter writer = null;
//writer = new BufferedWriter(new FileWriter("OutputLatest.txt"));
for (Integer i : inputArray) {
System.out.println(i);
// Writing sorted lines into output file
//writer.write(i);
//writer.newLine();
}
} catch (IOException ie) {
System.out.print(ie.getMessage());
}
}
}
您的递归调用是从从和中的中间 1到右，如下所示：
count = _mergeSort(arr, temp, left, mid);
count += _mergeSort(arr, temp, mid+1, right);
因此，正确的合并函数调用应为：
count += merge(arr, temp, left, mid, right);
合并定义中也有一些错误。让我向您指出：
x应从left到mid不等。y应该从mid+1到right
x = left; /* i is index for left subarray*/
y = mid+1; /* j is index for right subarray*/
z = left; /* k is index for resultant merged subarray*/
while ((x <= mid) && (y <= right))
同样，反转计数实际上是 count = count (MID -x( 1; 。您可以通过取5个元素的小数组来弄清楚这一点。
temp 的索引始终从0 开始。
因此，正确的合并函数是：
static int merge(Integer arr[], int temp[], int left, int mid, int right)
{
int x, y, z ;
int count = 0;
x = left; /* i is index for left subarray*/
y = mid+1; /* j is index for right subarray*/
z = 0; /* k is index for resultant merged subarray*/
while ((x <= mid) && (y <= right))
{
if (arr[x] <= arr[y])
{
temp[z++] = arr[x++];
}
else
{
temp[z++] = arr[y++];
count = count + (mid - x) + 1;
}
}
/* Copy the remaining elements of left subarray
(if there are any) to temp*/
while (x <= mid)
temp[z++] = arr[x++];
/* Copy the remaining elements of right subarray
(if there are any) to temp*/
while (y <= right)
temp[z++] = arr[y++];
/*Copy back the merged elements to original array*/
z = 0;
for (x=left; x <= right; x++)
arr[x] = temp[z++];
return count;
}
这是 hackerrank /练习/教程/破解编码访谈/合并排序的任务：counting倒置：：
static long mergeSort(int[] arr, int l, int r) {
long swaps = 0;
if (l < r) {
int p = (l + r) / 2;
swaps += mergeSort(arr, l, p);
swaps += mergeSort(arr, p + 1, r);
// Merge
int[] la = Arrays.copyOfRange(arr, l, p + 1);
int[] ra = Arrays.copyOfRange(arr, p + 1, r + 1);
int i = l, lai = 0, rai = 0;
while (lai < la.length && rai < ra.length) {
if (ra[rai] < la[lai]) {
arr[i++] = ra[rai++];
swaps += la.length - lai;
} else {
arr[i++] = la[lai++];
}
}
while (lai < la.length) {
arr[i++] = la[lai++];
}
while (rai < ra.length) {
arr[i++] = ra[rai++];
}
}
return swaps;
}
在 inv_count使用长而不是int。另外，将返回类型从int更改为长。
与上述解决方案一样，int溢出。
您的代码中有多个问题：
- 您使用类型
int来计算反转数。类型int的最大值为2147483647。相反，您应该使用类型long，该类型可以处理最多可9223372036854775807的值。 -
您在
main()方法中两次致电mergeSort，带有冲突的数组大小：inversioncount.mergeSort(inputArray, inputArray.length - 1); System.out.println("Number of inversions are " + mergeSort(inputArray, inputArray.length));您应该只用正确的长度调用一次：
long inversion_count = mergeSort(inputArray, inputArray.length); System.out.println("Number of inversions is " + inversion_count + "n"); -
将
right指定为切片中最后一个元素的索引是令人困惑的。一种更常规和惯用的方法使用right作为切片末端的第一个元素的索引。
这是一个更正的版本：
package com.inversioncount;
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
public class inversioncount {
public static long mergeSort(Integer[] arr, int array_size) {
int temp[] = new int[array_size];
return _mergeSort(arr, temp, 0, array_size);
}
/* An auxiliary recursive method that sorts a slice of the input array and
returns the number of inversions. */
static long _mergeSort(Integer arr[], int[] temp, int left, int right) {
long count = 0;
if (right - left > 1) {
/* Divide the array into two parts and call _mergeSort() for each of the parts */
int mid = (right + left + 1) / 2;
/* Inversion count will be sum of inversions in left-part, right-part
and number of inversions in merging */
count += _mergeSort(arr, temp, left, mid);
count += _mergeSort(arr, temp, mid, right);
/* Merge the two parts */
count += merge(arr, temp, left, mid, right);
}
return count;
}
/* This method merges two sorted slices of the array and returns the inversion count */
static long merge(Integer arr[], int temp[], int left, int mid, int right) {
long count = 0;
int x = left; /* x is index for left subarray */
int y = mid; /* y is index for right subarray */
int z = left; /* z is index for resultant merged subarray */
while (x < mid && y < right) {
if (arr[x] <= arr[y]) {
temp[z++] = arr[x++];
} else {
temp[z++] = arr[y++];
count += mid - x;
}
}
/* Copy the remaining elements of left subarray if any */
while (x < mid)
temp[z++] = arr[x++];
/* Copy the remaining elements of right subarray if any */
while (y < right)
temp[z++] = arr[y++];
/* Copy back the merged elements to original array */
for (x = left; x < right; x++)
arr[x] = temp[x];
return count;
}
// Driver method to test the above function
public static void main(String[] args) throws FileNotFoundException {
try {
BufferedReader br = new BufferedReader(new FileReader("IntegerArray.txt"));
List<Integer> lines = new ArrayList<Integer>();
String line;
while ((line = br.readLine()) != null) {
lines.add(Integer.parseInt(line));
}
br.close();
Integer[] inputArray = lines.toArray(new Integer[lines.size()]);
long inversion_count = mergeSort(inputArray, inputArray.length);
System.out.println("Number of inversions is " + inversion_count + "n");
//BufferedWriter writer = null;
//writer = new BufferedWriter(new FileWriter("OutputLatest.txt"));
for (Integer i : inputArray) {
System.out.println(i);
// Writing sorted lines into output file
//writer.write(i);
//writer.newLine();
}
} catch (IOException ie) {
System.out.print(ie.getMessage());
}
}
}