不尋常的合併排序失敗

我有一個不尋常的問題。我一直在實現合併排序並遇到以下情況：除了最後一次傳遞之外，該方法正常工作。給定一個隨機的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

不尋常的合併排序失敗

回答

相關問題