1

我正在尝试创建 MergeSort 的非递归版本，但由于某种原因，合并使代码无法完整运行。

合并排序代码：

public void mergeSort(int[] input)
{

    int n = input.length;
    int size;
    int l;
    for (size = 1; size <= n-1; size = 2*size)
    {
        for (l = 0; l < n-1; l += 2*size)
        {
            int m = l + size -1;
            int r = minimum(l + 2*size - 1, n-1);
            merge(input, l, m, r);
        }
    }       
}

合并代码：

public static void merge(int[] numbers, int low, int middle, int high)
{

    // Copy both parts into the helper array
     int helper[];
    helper = new int[numbers.length];

   for (int i = low; i <= high; i++) {
       helper[i] = numbers[i];
   }


   int i = low;
   int j = middle + 1;
   int k = low;
   // Copy the smallest values from either the left or the right side back
   // to the original array

   while (i <= middle && j <= high) {
       if (helper[i] <= helper[j]) {
            numbers[k] = helper[i];
            i++;
       } else {
            numbers[k] = helper[j];
            j++;
       }

       k++;
     }
     // Copy the rest of the left side of the array into the target array

     while (i <= middle) {
           numbers[k] = helper[i];
           k++;
           i++;
     }
 }

这就是我填充输入数组（大小为 100）的方式：

public static int fillArray()
{
    Random r = new Random();
    int rand = r.nextInt();
    return rand;
}
 //followed by these lines of code in the main method:

    int[] arr;

    arr = new int[100];

    for(int i =0; i<arr.length; i++)
    {
        arr[i] = fillArray();
    }

例外是numbers[k] = helper[i]in merge()。

我知道输入数组的内容很好，因为我在对其执行 MergeSort 之前打印出数组的内容。有谁知道问题是什么？

4

2 回答 2

0

m像这样修复mergeSort()：

int m = Math.min(l + size - 1, n - 1);
于 2015-09-14T05:05:37.677 回答
0

你没有提到你得到了什么异常，但我认为它的数组超出了范围。是什么阻止你的中间变量超过数组的大小？

while (i <= middle) {
   numbers[k] = helper[i];
   k++;
   i++;
}

放入调试打印等。

于 2015-09-14T04:57:46.923 回答