自底向上的有序队列并归并

题目要求，每个数组元素放置到一个队列中，再生成一个队列，存储这些只包含一个元素的队列，最终排序。

比较简单，按自底向上那个例子，先两两合并，再四四合并，以此类推。

将数组生成队列的队列：

private static Queue<Queue<Integer>> generateQueue(Integer[] a)
{
    Queue<Queue<Integer>> q = new Queue<>();
    for (int i = 0; i < a.length; i++)
    {
        Queue<Integer> q1 = new Queue<>();
        q1.enqueue(a[i]);
        q.enqueue(q1);
    }

    return q;
}

merge就用2.2.14的方法：

private static Queue<Integer> merge(Queue<Integer> a, Queue<Integer> b)
{
    Queue<Integer> q = new Queue<>();
    while (!a.isEmpty() || !b.isEmpty())
    {
        if (a.isEmpty())
        {
            while (!b.isEmpty())
            {
                q.enqueue(b.dequeue());
            }
        }
        else if (b.isEmpty())
        {
            while (!a.isEmpty())
            {
                q.enqueue(a.dequeue());
            }
        }
        else // 都不为空
        {
            int a1 = a.peek();
            int b1 = b.peek();
            if (a1 <= b1)
            {
                q.enqueue(a.dequeue());
            }
            else // a1 > b1
            {
                q.enqueue(b.dequeue());
            }
        }
    }

    return q;
}

sort方法：

private static Queue<Integer> sort(Queue<Queue<Integer>> q)
{
    //进行lgN次两两归并
    int N = q.size();
    StdOut.println("数组长度：N: " + N);
    // 外层循环，分别是1, 2, 4
    for (int sz = 1; sz < N; sz = sz + sz)
    {
        int n2 = N - sz;
        StdOut.println("sz: " + sz + " n2: " + n2);

        for (int lo = 0; lo < n2; lo += (sz + sz))
        {
            int diff = N - lo;
            if (diff >= 2)
            {
                var q1 = q.dequeue();
                var q2 = q.dequeue();
                var q3 = merge(q1, q2);
                q.enqueue(q3);
            }
            else
            {
                var q1 = q.dequeue();
                q.enqueue(q1);
            }
        }

        StdOut.println();
    }

    return q.dequeue();
}

通过在原队列上操作，最后只会包含这个元素，返回这个元素，它是Queue类型，就是已排序类型：

public static void main(String[] args)
{
    Integer[] a = {1, 4, 3, 9, 8, 2, 6, 1, 5};
    Queue<Queue<Integer>> q = generateQueue(a);
    var result = sort(q);
    show(result);

    StdOut.println();
}

执行输出结果为：

数组长度：N: 9
1 1 2 3 4 5 6 8 9