java - Java中的非递归归并排序

Question

我正在为我的 CS 类开发非递归合并排序，但它并不完全有效。我知道它正在被调用，因为当我运行测试程序时它会更改数组，只是没有更改为正确的顺序。有人可以帮忙吗？谢谢!

private static void mergeSort(int[] a, int left, int right)
{
    int midPoint = ((right + left) / 2);
    int[] buffer = new int[19];

    selectionSort(a, left, midPoint);
    selectionSort(a, midPoint-1, right);
    merge(a, buffer, 0, 9, 19);
}

private static void selectionSort(int[] a, int beginning, int end)
{
    int [] temp = new int[end-1];

    for(int y = 0; y < end - 1; y++)
    {
        temp[y] = a[y]; 
    }

    for (int i = 0; i < temp.length - 1; i++)
    {
        int minIndex = findMinimum(temp, i);
        if (minIndex != i)
            swap (temp, i, minIndex);
    }
}

private static int findMinimum(int[] a, int first)
{
    int minIndex = first;

    for (int i = first + 1; i < a.length; i++)
    {
        if (a[i] < a[minIndex])
            minIndex = i;
    }
    return minIndex;
}

private static void swap(int []a, int x, int y)
{
    int temp = a[x];
    a[x] = a[y];
    a[y] = temp;
}

private static void merge(int[] a, int[] temp, int left, int mid, int right) {
    if (mid >= a.length) return;
    if (right > a.length) right = a.length;
    int i = left, j = mid+1;
    for (int k = left; k < right; k++) {
       if      (i == mid)     
           temp[k] = a[j++];
       else if (j == right)      
           temp[k] = a[i++];
       else if (a[j] < a[i])  
           temp[k] = a[j++];
       else                   
           temp[k] = a[i++];
    }
    for (int k = left; k < right; k++)
       a[k] = temp[k];
 }

Answer 1

可能还有其他错误，但最突出的一个错误是 selectionSort 实际上并未对数组执行任何操作。您传入一个数组引用作为 a 参数:

private static void selectionSort(int[] a, int beginning, int end)

由于这是一个引用，如果 selectionSort 执行任何操作来分配给 a 的任何元素，例如

a[x] = y;

它会改变调用者数组的元素，就像你想要的那样。但是 selectionSort 中没有任何语句可以更改 a 中的任何内容。该代码将元素复制到 temp，与 temp 一起使用 - 但随后会丢弃所有工作。