java - 用户输入抛出 NegativeArraySizeException；相同的硬编码(均为正数)数字有效

Question

我目前正在研究迭代合并排序，它会在排序前询问用户要生成多少个数字。如果我输入大于 10 的数字，我会收到错误消息:“线程“主”java.lang.NegativeArraySizeException 中的异常”，但如果我硬编码相同的确切数字(均为正数)，程序将按预期运行。为什么会出现此错误，我该如何解决？提前感谢您的帮助。

演示文件:

import java.util.Scanner;

public class MergeSortDemo
{
    public static void main(String[] args)
    {
        Scanner keyboard = new Scanner(System.in);

        //int arraySize = 17;
        int arraySize = MergeSortAlgorithms.getArraySize(keyboard);
        int[] testArray = new int[arraySize];



        MergeSortAlgorithms.fillArray(testArray);
        MergeSortAlgorithms.printArray(testArray);
        MergeSortAlgorithms.mergeSort(testArray);
        MergeSortAlgorithms.printArray(testArray);
    }//ends main
}//ends class

迭代合并排序:

    public static void mergeSort(int arr[])
    {
        int n = arr.length;
        // For current size of subarrays to
        // be merged curr_size varies from
        // 1 to n/2
        int curr_size;

        // For picking starting index of
        // left subarray to be merged
        int left_start;


        // Merge subarrays in bottom up
        // manner. First merge subarrays
        // of size 1 to create sorted
        // subarrays of size 2, then merge
        // subarrays of size 2 to create
        // sorted subarrays of size 4, and
        // so on.
        for (curr_size = 1; curr_size <= n-1;
                    curr_size = 2*curr_size)
        {

            // Pick starting point of different
            // subarrays of current size
            for (left_start = 0; left_start < n-1;
                        left_start += 2*curr_size)
            {
                // Find ending point of left
                // subarray. mid+1 is starting
                // point of right
                int mid = left_start + curr_size - 1;

                int right_end = Math.min(left_start
                            + 2*curr_size - 1, n-1);

                // Merge Subarrays arr[left_start...mid]
                // & arr[mid+1...right_end]
                merge(arr, left_start, mid, right_end);
            }
        }
    }

    public static void merge(int arr[], int l, int m, int r)
    {
        int i, j, k;
        int n1 = m - l + 1;
        int n2 = r - m;

        /* create temp arrays */
        int L[] = new int[n1];
        int R[] = new int[n2];

        /* Copy data to temp arrays L[]
        and R[] */
        for (i = 0; i < n1; i++)
            L[i] = arr[l + i];
        for (j = 0; j < n2; j++)
            R[j] = arr[m + 1+ j];

        /* Merge the temp arrays back into
        arr[l..r]*/
        i = 0;
        j = 0;
        k = l;
        while (i < n1 && j < n2)
        {
            if (L[i] <= R[j])
            {
                arr[k] = L[i];
                i++;
            }
            else
            {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        /* Copy the remaining elements of
        L[], if there are any */
        while (i < n1)
        {
            arr[k] = L[i];
            i++;
            k++;
        }

        /* Copy the remaining elements of
        R[], if there are any */
        while (j < n2)
        {
            arr[k] = R[j];
            j++;
            k++;
        }
    }

数组相关方法:

    public static int getArraySize(Scanner keyboard)
    {
        System.out.printf("How many numbers would you like to generate? \n(More Numbers = Longer Sort): ");
        int returnValue = keyboard.nextInt();

        return returnValue;
    }

    public static void fillArray(int[] array)
    {
        Random random = new Random();

        for(int i = 0; i < array.length; i++)
        {
            int randomNumber = (int)(Math.random() * 700 + 1);
            array[i] = randomNumber;
        }
    }

损坏的输出(数组大小为 17):

How many numbers would you like to generate?
(More Numbers = Longer Sort): 17
241 272 539 456 242 571 333 28 292 426 7 595 191 162 1 542 394
Exception in thread "main" java.lang.NegativeArraySizeException
        at MergeSortAlgorithms.merge(MergeSortAlgorithms.java:125)
        at MergeSortAlgorithms.mergeSort(MergeSortAlgorithms.java:112)
        at MergeSortDemo.main(MergeSortDemo.java:17)
Press any key to continue . . .

相同的输出，但 17 是硬编码的数组大小:

175 423 562 133 136 53 265 605 312 169 666 630 641 613 176 568 111
53 111 133 136 169 175 176 265 312 423 562 568 605 613 630 641 666
Press any key to continue . . .

编辑:经过更多测试后，某些更大的数字确实有效。例如，25、30 和 56 按预期工作。

Answer 1

这与从控制台获取输入无关。相反，您的代码中存在错误。

int mid = left_start + curr_size - 1;
int right_end = Math.min(left_start + 2*curr_size - 1, n-1);

考虑上面的线条。每当 left_start + 2*curr_size - 1 足够大于 n-1 时，right_end 的值将变得小于 mid.

在这种情况下，merge() 方法中 n2 的值变为负数。因此错误。一旦你纠正了这个问题，你就会解决问题。

更新我添加了一些 if 条件。这是工作代码。

public static void mergeSort(int arr[])
{
    int n = arr.length;
    // For current size of subarrays to
    // be merged curr_size varies from
    // 1 to n/2
    int curr_size;

    // For picking starting index of
    // left subarray to be merged
    int left_start;


    // Merge subarrays in bottom up
    // manner. First merge subarrays
    // of size 1 to create sorted
    // subarrays of size 2, then merge
    // subarrays of size 2 to create
    // sorted subarrays of size 4, and
    // so on.
    for (curr_size = 1; curr_size <= n-1;
                curr_size = 2*curr_size)
    {

        // Pick starting point of different
        // subarrays of current size
        for (left_start = 0; left_start < n-1;
                    left_start += 2*curr_size)
        {
            // Find ending point of left
            // subarray. mid+1 is starting
            // point of right
            int mid = left_start + curr_size - 1;

            int right_end = Math.min(left_start
                        + 2*curr_size - 1, n-1);

            if(right_end<mid)
                right_end=mid;

            // Merge Subarrays arr[left_start...mid]
            // & arr[mid+1...right_end]
            merge(arr, left_start, mid, right_end);
        }
    }
}

public static void merge(int arr[], int l, int m, int r)
{
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;

    /* create temp arrays */
    int L[] = new int[n1];
    int R[] = new int[n2];

    /* Copy data to temp arrays L[]
    and R[] */
    for (i = 0; i < n1; i++)
        if(l+i<arr.length)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        if(l+j<arr.length)
        R[j] = arr[m + 1+ j];

    /* Merge the temp arrays back into
    arr[l..r]*/
    i = 0;
    j = 0;
    k = l;
    while (i < n1 && j < n2)
    {
        if (L[i] <= R[j])
        {
            arr[k] = L[i];
            i++;
        }
        else
        {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    /* Copy the remaining elements of
    L[], if there are any */
    while (i < n1 && i<n1 && k<arr.length)
    {
        arr[k] = L[i];
        i++;
        k++;
    }

    /* Copy the remaining elements of
    R[], if there are any */
    while (j < n2)
    {
        arr[k] = R[j];
        j++;
        k++;
    }
}

不过，我觉得您可以简化代码。