合并排序：为什么我的合并方法只向队列中添加一个数字？

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

合并排序：为什么我的合并方法只向队列中添加一个数字？

Merge sort: Why does my merge method only add one number to the queue?

java

queue

recursion

mergesort

linked-list