用户输入抛出负数组大小异常;相同的硬编码(均为正数)数字有效

Question

我目前正在进行迭代合并排序，它要求用户在排序之前生成多少个数字。如果我输入一个数字>10，我会收到错误："线程 'main' 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

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

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

不过，我觉得你简化了代码。

Answer 2

我尝试运行您的代码。它运行得很完美。这是控制台上的输出。

How many numbers would you like to generate? 
(More Numbers = Longer Sort): 17
[303, 394, 315, 436, 196, 212, 629, 139, 666, 519, 4, 182, 36, 108, 129, 490, 174]
[4, 36, 108, 129, 139, 174, 182, 196, 212, 303, 315, 394, 436, 490, 519, 629, 666]

:)没有例外