java - 异常的合并排序失败

Question

我有一个不寻常的问题。我一直在实现 Merge Sort 并遇到以下情况:除了最后一次通过外，该方法工作正常。给定一个随机 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 .