sorting - 用另一个队列对队列进行排序

Question

如何仅使用另一个大小为 N 的队列和有限数量的变量对大小为 N 的队列进行排序？

天真的实现 - 找到队列的最小值并将其推送到空队列，然后找到新的最小值并将其推送等是 O(n^2)。有没有更有效的算法？

Answer 1

我不认为天真的实施会奏效。这是一个队列，所以如果最小的元素不在队列的末尾，你就不能删除它。

我能想到的唯一方法是：始终保持第二个队列排序。1. 从 q1 中删除元素。2. 如果此元素>= q2 的最后一个元素，则将其插入到 q2 中。（这样 q2 仍然排序）。3. 否则，将其插回 q1。继续重复上述步骤，直到 q1 为空。

Answer 2

我的算法：

 let the Q size = n, 
 1 save = getRearValue(1stQ)
 2 pop the element from 1st Q and insert it into 2nd Q.
 3 if getFrontValue(1stQ) > getRearValue(2ndQ)  
 4        then goto step 2.
 5 else 
 6        pop the element from 1st Q and insert back into the same Q (1st Q). 
 7        if (save != getRearValue(1stQ)) goto step 3.
 8 if (1st Q not sorted OR getFrontValue(1stQ) > getFrontValue(2ndQ))
 9          then 
 10          pop all elements of 2nd Q and insert into 1st Q (One by one).
 11          goto step 1.
 12 else
 13     pop all elements of 2nd Q and insert into 1st Q (One by one).
 14     return 1stQ

Answer 3

这是我认为可能有效的方法：-

该算法使用递归对队列进行排序。

假设我们有一个函数 copy_from 可以从一个队列复制到另一个队列，如下所示：-

void copy_from (ArrayQueue&Q_from,ArrayQueue& Q_to){

     while(!Q_from.empty()){

        int t= Q_from.front();
        Q_to.enqueue(t);
        Q_from.dequeue();
     }

}   

主要排序功能如图：-

    void sort(ArrayQueue &Q, int element, ArrayQueue&Q2){

if(Q.size()==1){

    if(Q.front()>element){

         int front = Q.front();
         Q.dequeue();
         Q.enqueue(element);
         Q.enqueue(front);      
    }
    else{
        Q.enqueue(element);
    }

}
else{

 int front = Q.front();
 Q.dequeue();
 sort(Q,front); // sort the remaining queue.

 int sorted_front = Q.front(); //get front element of sorted queue
 if(element<sorted_front){

    Q2.enqueue(element);
    copy_from(Q,Q2);
    copy_from(Q2,Q);     

 }
 else{
    // dequeue all elements from the queue which are lesser than element and put it into new queue.
    // Then enqueue the new element
    // Then enqueue whatevers bigger than element into the queue.

      Q2.enqueue(sorted_front);
      Q.dequeue();

      while(!Q.empty()&&Q.front()<element){
         Q2.enqueue(Q.front());
         Q.dequeue();
      }

      Q2.enqueue(element);
      copy_from(Q,Q2);
      copy_from(Q2,Q);

 }

}
}

当我们最初调用排序函数时，我们可以这样调用它：-

Queue Q, Q2;

 int front = Q.front();
 Q.dequeue();
 sort(Q,front,Q2);

如果我们输入为 6->4->9>2->1，则结果将是 9->6->4->2->1。

Answer 4

这是我从头顶想到的一个简单逻辑。最坏情况的运行时间是 O(N^2)，而理想情况下最好的情况是 O(N)。我认为可以通过即兴逻辑进一步降低复杂性。

语法是 Javascript，但很好的注释是不言自明的。

我希望这有帮助。

// SORT A QUEUE USING ANOTHER QUEUE
function sortQueueUsingQueue(uq) {
    // instantiate required variables
    var sq = new Queue();
    var t = null, last = null;
    // copy the items to a temp queue
    // so as not to destroy the original queue
    var tq = new Queue(uq);
    // loop until input is not empty
    while(!tq.isEmpty()) {
        t = tq.dequeue();
        if (last && last <= t) {
            // new element will be at the end of the queue, and we don't have to
            // process any further - short-circuit scenario
            // this is the best case scenario, constant time operation per new item
            sq.enqueue(t);
            // also keep track of the last item in the queue,
            // which in this case is the new item
            last = t;
        } else {
            // other scenario: linear time operation per new item
            // new element will be somewhere in the middle (or beginning) so,
            // take elements from the beginning which are less or equal to new item,
            // and put them at the back
            while(!sq.isEmpty() && sq.peek() <= t) {
                sq.enqueue(sq.dequeue());
            }
            // when that is done, now put the new element into the queue,
            // i.e the insertion into the proper place
            sq.enqueue(t);
            // following which, shift the rest elements to the back of the queue,
            // to reconstruct the sorted order,
            // thus always keeping the second queue sorted per insertion
            while(sq.peek() > t) {
                // meanwhile, also keep a track of the last (highest) item in the queue
                // so that we may perform a short-circuit if permitted
                last = sq.dequeue();
                sq.enqueue(last);
            }
        }

    }
    return sq;
}

您可以在此处将整个工作代码视为 github要点：https ://gist.github.com/abhishekcghosh/049b50b22e92fefc5124