不寻常的合并排序失败

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);

您可以在此处查看工作代码(在更改之后).