不寻常的合并排序失败

我有一个不寻常的问题。我一直在实现合并排序并遇到以下情况：除了最后一次传递之外，该方法正常工作。给定一个随机的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]); 
}

来源

2011-05-12 Techrocket9

您应该使用'int []'，让Java在处理使用'LinkedList'和'PriorityQueue'的时候处理自动装箱。 – 2011-05-12 14:59:52

问题出在您的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部分，这将从虽然你应该从sFirstpoll()。应该是returner列表中的第一个要添加的元素，而不是4。

而且（基于ccoakley答案）的变化，你应该使用mergeSort()返回数组，这可以很容易地做到：

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

你可以看看的工作代码（修改后） here。

来源

2011-05-12 16:06:17 insumity

谢谢，这解决了这个问题。 – Techrocket9 2011-05-12 21:58:19

我希望这有助于：为什么你要归并返回一个整数数组，但随后在你的电话不能使用返回值来归并（第一）和归并（二）？

它看起来好像是你的代码的一部分被写入来对传入的值进行排序，而部分被写入以返回一个有序数组。

来源

2011-05-12 15:35:35 ccoakley

不寻常的合并排序失败

回答

相关问题