排序算法 - java 排序堆栈

Question

这是我想出的：

procedure sort(Stack S, Queue Q, sortedPosition)
    if(sortedPosition==0)
        // Sorting completed
        return;

    max = S.pop
    currentPosition = 0;

    while (!S.isEmpty()) do:
        currentPosition = currentPosition + 1;
        if(currentPosition < sortedPosition)
            current = S.pop();
            if(current > max)
                Q.add(max);
                max = current;
            else
                Q.add(current);
            end if
        end if

    end while

    S.push(max);
    currentPosition--;

    while (!Q.isEmpty()) do:
        S.push(Q.remove());
    end while


    sort(S, Q, currentPosition);
end procedure

有人可以看看我做错了什么吗？另外，最坏的情况运行时间必须是 O(n^2).

Answer 1

这个问题问得好。 我亲自检查了你的解决方案，它进入了无限循环，但你的方法非常好。我稍微修改了你使用的逻辑。我尽量保留你的方法。

我改变的逻辑是首先我将所有堆栈元素复制到队列。然后我用我的登录过滤队列，把最高的元素一个一个插入栈中。一旦一个元素（按排序顺序）被推入堆栈，相应的元素就会从队列中删除。

请检查我在 java 上完成的以下解决方案。希望对你有所帮助..

您必须（第一次）使用参数 i 调用排序方法。主堆栈，ii。一个空队列，并且 iii.the 没有元素（堆栈的大小）..

Stack sort(Stack<Integer> s,Queue<Integer> q,int length)
    {

        if(length==0)
        {
            return s;
        }

        if(q.isEmpty())
        {
            while(!s.empty())
            {
                q.add(s.pop());
            }
        }

        int stckElement;
        int qElement;
        s.push(q.remove());

        int count=0;
        while(count<length-1)
        {
            stckElement=s.pop();
            qElement=q.remove();
            if(stckElement<qElement)
            {
                s.push(qElement);
                q.add(stckElement);
                count=0;
            }else
            {
                s.push(stckElement);
                q.add(qElement);
                count++;
            }
        }

        length--;
        return sort(s,q,length);
    }

Answer 2

可以使用队列和堆栈实现自下而上的合并排序 O(n log(n))。首先，所有元素都从堆栈弹出到队列中（这反转了元素）。队列将被反向排序（反转比较的意义）。第一个合并通道从队列中弹出一个元素并将其推入堆栈，比较 queue.front() 与 stack.top()，弹出并将较小的元素推入队列，然后弹出并推入另一个，重复直到合并所有元素对，在队列中创建大小为 2 的已排序运行s。然后为下一次设置，循环队列以反转所有偶数运行s（除非最后有一个单独的偶数运行而没有奇数运行合并，在这种情况下它是只是复制而不是反转）：来自队列的偶数运行s 被压入堆栈，然后从堆栈弹出并压入队列以反转它们，奇数运行s 从队列中弹出并压入队列以复制他们按顺序。对于剩余的传递，运行对通过从队列中弹出一个偶数运行并将其推入堆栈，"unreversing" 将其压入堆栈，然后偶数运行在stack.top() 与 queue.front() 处的奇数运行合并，将合并的运行推回队列。一旦合并所有对，运行大小加倍，如果运行大小 < queue.size()，则队列再次循环以反转所有偶数运行和合并过程重复; else 运行 size >= queue.size() 并且队列被排序（反向）。反向排序队列被弹出并推入堆栈，创建一个排序堆栈。

我试图找出一种方法来在合并期间反转比较的意义，以避免在每次合并通过后甚至运行s 循环都必须进行反转，但这是一个递归模式，我无法弄清楚如何通过迭代进行复制。无论如何，更简单的 reverse even 运行s 方法似乎足够快。

在我的系统上，Intel 2600K 3.4 ghz，Visual Studio 发布版本，此方法可以在大约 2.8 秒内对 400 万个伪随机 32 位无符号整数进行排序。

堆栈升序排序的示例代码（降序比较的反向意义）。 ll、rr 和 ee 是伪索引，以保持运行计数逻辑与数组/向量自下而上合并排序相同。实际合并对左/偶运行使用堆栈，对右/奇运行.

使用队列的一部分

typedef unsigned int uint32_t;

void sqsort(std::stack <uint32_t> &s , std::queue <uint32_t> &q)
{
    size_t n = s.size();
    while(!s.empty()){                      // pop/push s to q
        q.push(s.top());
        s.pop();
    }
    // merge sort usign stack and queue
    size_t r = 1;
    while(1){
        size_t ee = 0;                      // pseudo end index
        // merge pass
        while(ee < n){
            size_t ll = ee;                 // ll = pseudo start of left  run
            size_t rr = ll+r;               // rr = pseudo start of right run
            if(rr >= n){                    // if only left run
                while(ll++ < n){            //   copy it and break
                    q.push(q.front());
                    q.pop();
                }
                break;
            }
            ee = rr+r;                      // ee = pseudo end of right run
            if(ee > n)
                ee = n;
            // merge a pair of runs
            // stack == left / even run
            // queue == right / odd run
            size_t m = rr - ll;             // m = # elements in left run
            while(m--){                     //  pop/push left run to stack
                s.push(q.front());
                q.pop();
            }
            m = ee - rr;                    // m = # elements in right run
            while(1){
                if(q.front() > s.top()){    // (reverse for descending)
                    q.push(q.front());
                    q.pop();
                    if(--m == 0){           // if end right run
                        while(!s.empty()){  //   copy rest of left run
                            q.push(s.top());
                            s.pop();
                        }
                        break;              //   and break
                    }
                } else {
                    q.push(s.top());
                    s.pop();
                    if(s.empty()){          // if end left run
                        while(m--){         //   copy rest of right run
                            q.push(q.front());
                            q.pop();
                        }
                        break;              // and break
                    }
                }
            }                               // end merge pair
        }                                   // end merge pass
        r *= 2;                             // double run size
        if(r >= n)                          //  break if sort done
            break;
        // reverse left/even runs in q
        ee = 0;                             // pseudo end index
        while(ee < n){
            size_t ll = ee;                 // ll = pseudo start of left  run
            size_t rr = ll+r;               // rr = pseudo start of right run
            if(rr >= n){                    // if only left run
                while(ll++ < n){            //   copy it and break
                    q.push(q.front());
                    q.pop();
                }
                break;
            }
            ee = rr+r;                      // ee = pseudo end of right run
            if(ee > n)
                ee = n;
            size_t m = rr - ll;             // m = # elements in left run
            while(m--){                     // pop/push left run to s
                s.push(q.front());
                q.pop();
            }
            while(!s.empty()){              // pop/push s to q
                q.push(s.top());            //  (reverse left/even run)
                s.pop();
            }
            m = ee - rr;                    // m = # elements in right run
            while(m--){                     // copy odd run to q
                q.push(q.front());
                q.pop();
            }
        }                                   // end reverse left/even runs
    }                                       // end merge sort
    while(!q.empty()){                      // pop/push q to s
        s.push(q.front());
        q.pop();
    }
}

Answer 3

如果您随时使用小于堆栈中元素数的 sortedPosition 调用该过程，您的算法将包含一个无限循环，因为：增加 [= 后您将达不到 current = S.pop(); 13=] 的次数等于 sortedPosition 那么你就违反了 if 条件并且堆栈不为空，那么你将继续增加 currentPositionm 这是肯定的。

在 while 之后，您应该设置 sortedPosition--; 而不是 currentPosition--;，然后为 sortedPosition 而不是 currentPosition 调用 sort，在第一次调用，应该等于元素个数。

正确的实现应该是：

procedure sort(Stack S, Queue Q, sortedPosition)
if(sortedPosition==0)
    // Sorting completed
    return;

max = S.pop
currentPosition = 0;

while (currentPosition < sortedPosition) do:
    if(currentPosition < sortedPosition)
        current = S.pop();
        if(current > max)
            Q.add(max);
            max = current;
        else
            Q.add(current);
        end if
    end if
    currentPosition = currentPosition + 1;
end while

S.push(max);
sortedPosition--;

while (!Q.isEmpty()) do:
    S.push(Q.remove());
end while


sort(S, Q, sortedPosition);
end procedure

排序算法 - java 排序堆栈

Sorting Algorithm - java sorting stacks

sorting

algorithm

queue

stack