Java中的非递归合并排序

I am working on a non recursive merge sort for my CS class and it is not exactly working. I know it is being called since when I run the test program it changes the array, just not into the correct order. Can someone please help? Thanks!

我正在为我的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];
 }

1 个解决方案

#1

There may be other bugs, but one that sticks out is that selectionSort doesn't actually do anything to the array. You pass in an array reference as the a parameter:

可能还有其他错误，但突出的是，selectionSort实际上并没有对数组做任何事情。您传入一个数组引用作为参数：

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

Since this is a reference, if selectionSort did anything to assign to any elements of a, like

由于这是一个引用，如果selectionSort做了任何事情来分配给a的任何元素，比如

a[x] = y;

it would change the element of the caller's array, like you want. But there is no statement in selectionSort that changes anything in a. The code copies elements to temp, works with temp--but then throws all the work away.

它会像你想要的那样改变调用者数组的元素。但是，selectionSort中没有任何声明可以改变a中的任何内容。代码将元素复制到temp，使用temp - 然后抛弃所有的工作。

#1