java异常合并排序失败

Question

我有一个不寻常的问题。我一直在实现合并排序，并遇到了以下问题：除了最后一次，该方法工作正常。给定一个随机Integer数组作为输入，返回一个Integer数组，其中前半部分和后半部分分别排序。除最后一次外，合并工作正常。在摆弄调试器几个小时后，我发现“提及点”总是在最后一次通过时计算为false，即使它不应该基于值

感谢所有的帮助

public static Integer[] mergeSort(Integer[] input)
{
    if (input.length == 1) return input;

    int splittle = input.length / 2;

    Integer[] first = new Integer[splittle];
    Integer[] second = new Integer[input.length - splittle];

    for (int i = 0; i < splittle; i++)
        first[i] = input[i];
    for (int i = splittle; i < input.length; i++)
        second[i - splittle] = input[i];

    mergeSort(first);
    mergeSort(second);

    LinkedList<Integer> returner = new LinkedList<Integer>();

    PriorityQueue<Integer> sFirst = new PriorityQueue<Integer>();
    PriorityQueue<Integer> sSecond = new PriorityQueue<Integer>();

    for (int i = 0; i < first.length; i++)
        sFirst.offer(first[i]);
    for (int i = 0; i < second.length; i++)
        sSecond.offer(second[i]);

    // while (!sFirst.isEmpty()&&!sSecond.isEmpty())
    // returner.add((sFirst.peek()>=sSecond.peek() ?
    // sFirst.poll():sSecond.poll()));

    // expansion of line above for debugging purposes

    while (!sFirst.isEmpty() && !sSecond.isEmpty())
    {
        int temp = 0;

        if (sFirst.peek() >= sSecond.peek())
            temp = sFirst.poll(); // Mention point
        else
            temp = sSecond.poll();
        returner.add(temp);

    }

    while (!sFirst.isEmpty())
        returner.add(sFirst.poll());
    while (!sSecond.isEmpty())
        returner.add(sSecond.poll());

    return returner.toArray(new Integer[0]);
}

Answer 1

问题出在while代码中，在使用poll()方法时更具体

你有：

if (sFirst.peek() >= sSecond.peek())
    temp = sFirst.poll(); // Mention point
else
    temp = sSecond.poll();

当你应该：

if (sFirst.peek() >= sSecond.peek())
    temp = sSecond.poll(); // Mention point
else
    temp = sFirst.poll();

之前，在这样的输入中：

sFirst = [-9, 1, 2, 9, 89] and  sSecond =  [4, 15, 18, 23, 31, 123]

你会有if (-9 >= 4)，这是错误的，所以你会做else部分，这将poll()来自sSecond，尽管你应该poll()来自sFirst-9应该是returner列表中要添加的第一个元素，而不是4

另外（基于ccoakley答案）更改，您应该使用从mergeSort()返回的数组，这可以通过以下方式轻松完成：

first = mergeSort(first);
second = mergeSort(second);

您可以查看工作代码（更改后）here

Answer 2

我希望这能有所帮助：为什么让mergeSort返回一个整数数组，但在调用mergeSort（第一个）和mergeSort（第二个）时不使用返回值

看起来，代码的一部分是为了对传入的值进行排序而编写的，另一部分是为了返回排序后的数组而编写的