使用至多2个队列实现O(n log n)时间复杂度的队列排序

嘿，你找对方向了——这个问题的核心确实是分治+归并的思路，只用队列的四个基础操作完全可以实现！给你几个关键的落地提示，帮你理清步骤：

1. 锚定归并排序的核心逻辑 #

归并排序的时间复杂度正好是O(n log n)，完美匹配需求，而队列的先进先出特性非常适配归并的「拆分-递归排序-合并」流程：

• 拆分：把原队列拆成两个子队列，递归排序每个子队列，直到子队列只有0或1个元素（天然有序）
• 合并：把两个有序子队列合并成一个有序队列，这一步完全能用队列的基础操作实现

2. 解决「没有size操作」的拆分问题 #

队列没有直接获取元素数量的方法，你可以这样统计并拆分：

• 把原队列的所有元素临时移到辅助队列，同时计数总元素数n，再把元素移回原队列
• 把原队列的前n/2个元素移到辅助队列（作为第二个子队列），剩下的留在原队列（作为第一个子队列）
• 这一步的时间是O(n)，但整个分治过程中每个元素只会被遍历log n次，总时间依然保持O(n log n)

3. 合并两个有序队列的具体操作 #

假设你有两个已排序的队列q1和q2，合并步骤如下：

• 准备一个临时队列result（可复用辅助队列）
• 当q1和q2都不为空时：
  • 比较q1.peek()和q2.peek()，把较小的元素从原队列出队，再入队到result
• 当其中一个队列为空后，把另一个队列剩余的所有元素依次出队并入队到result
• 最终result就是合并后的有序队列
• 这个合并操作的时间是O(k)（k为两个队列的总元素数），完全符合归并排序的复杂度要求

4. 递归框架伪代码参考 #

用伪代码帮你理清楚整体逻辑：

function sort_queue(q):
    if q.empty() or (判断q只有一个元素：比如出队一个元素后为空，再把元素放回):
        return q
    
    // 统计长度并拆分队列
    n = count_elements(q)  // 移到辅助队列计数后再移回原队列
    temp_q = empty queue
    for i from 0 to n/2 - 1:
        temp_q.enqueue(q.dequeue())
    
    // 递归排序两个子队列
    sorted_q1 = sort_queue(q)
    sorted_q2 = sort_queue(temp_q)
    
    // 合并有序队列
    return merge(sorted_q1, sorted_q2)

function merge(q1, q2):
    result = empty queue
    while not q1.empty() and not q2.empty():
        if q1.peek() <= q2.peek():
            result.enqueue(q1.dequeue())
        else:
            result.enqueue(q2.dequeue())
    
    // 处理剩余元素
    while not q1.empty():
        result.enqueue(q1.dequeue())
    while not q2.empty():
        result.enqueue(q2.dequeue())
    
    return result

小提醒 #

• 注意队列的复用，避免创建过多临时队列（题目允许用一个辅助队列，递归时灵活传递参数即可）
• 计数元素时一定要把元素移回原队列，别丢数据哦

内容的提问来源于stack exchange，提问作者Math.anony