异常合并排序失败

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< /code> 部分，它会从 sSecond 进行 poll()，尽管您应该从 sFirst 进行 poll()。 -9 应该是要添加到 returner 列表中的第一个元素，而不是 4。

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

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

您可以查看工作代码（更改后）此处。

Answer 2

我希望这会有所帮助：为什么您让 mergeSort 返回一个整数数组，但在调用 mergeSort(first) 和 mergeSort(second) 时不使用返回值？

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