合併排序：爲什麼我的合併方法只將一個數字添加到隊列中？

Question

這裏是我的代碼：

void mergeHelper(Queue<T> input1, Queue<T> input2, Queue<T> output) { 
      // TODO 4 
      if(!input1.isEmpty()) 
      { 
       T ip1 = input1.dequeue(); 
       if(!input2.isEmpty()) 
       { 
        T ip2 = input2.dequeue(); 
        if(ip1.compareTo(ip2)<=0) 
         output.enqueue(ip1); 
        else 
         output.enqueue(ip2); 
       } 
       else 
       { 
        output.enqueue(ip1); 
       } 
       mergeHelper(input1, input2, output); 
      } 
      else if(!input2.isEmpty()) 
      { 
       T ip2 = input2.dequeue(); 
       if(!input1.isEmpty()) 
       { 
        T ip1 = input1.dequeue(); 
        if(ip1.compareTo(ip2)<=0) 
         output.enqueue(ip1); 
        else 
         output.enqueue(ip2); 
       } 
       else 
       { 
        output.enqueue(ip2); 
       } 
       mergeHelper(input1, input2, output); 
      } 

    } 

這裏是一個臨時司機：

public class MergeDriver { 

    public static void main(String[] args) { 

     MergeSorter<Integer> ms = new MergeSorter<>(); 
     Queue<Integer> one = new Queue<>(); 
     Queue<Integer> two = new Queue<>(); 
     one.enqueue(new Integer(2)); 
     two.enqueue(new Integer(1)); 
     Queue<Integer> res = ms.merge(one, two); 
     System.out.println("The size of res is: "+ res.size()); 
     System.out.println("The value stored is: "); 
     while(!res.isEmpty()) 
      System.out.println((int)res.dequeue()); 
    } 

} 

只有1被添加到輸出隊列，其餘的不是。

生成的隊列大小始終爲1，並且僅將最小的元素添加到隊列中。我究竟做錯了什麼？

Answer 1

您的算法不正確，因爲它將兩個項目出列用於比較，但只將其中一個返回給輸出。

您可以通過在出列之前使用peek()方法來解決此問題，比較結果，然後僅將兩個元素中較小的元素出列並將其移入輸出。