java - 使用合并排序从文本文件中读取的 100000 个整数的反转计数。但无法获得正确的反转计数

Question

下面是我编写的代码，用于从文本文件中读取 100000 个整数并使用归并排序对它们进行排序。

问题:

1. 排序后的整数仅在 eclipse 控制台中以正确的顺序显示，但当我尝试将它们写入输出文本文件时，顺序发生了变化。

2. 据我所知，给定文本文件中的 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());
        }
    }
}

Answer 1

您的递归调用是从左到中和中+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;
}