java - 合并排序: Why does my merge method only add one number to the queue?

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() 来修复此问题出队之前的方法，比较结果，然后才将两个元素中较小的一个出队，并将其移动到输出中。