对堆栈中的值排序

Question

​

class CheckSort {
public static void sortStack(Stack<Integer> stack) {
    //1. Use a second tempStack.
    //2. Pop value from mainStack.
    //3. If the value is greater or equal to the top of tempStack, then push the value in tempStack
    //else pop all values from tempStack and push them in mainStack and in the end push value in tempStack and repeat from step 2.
    //till mainStack is not empty.
    //4. When mainStack will be empty, tempStack will have sorted values in descending order.
    //5. Now transfer values from tempStack to mainStack to make values sorted in ascending order.
    Stack<Integer> newStack = new Stack<>(stack.getMaxSize());
    while (!stack.isEmpty()) {
        Integer value = stack.pop();
        if (!newStack.isEmpty() && value >= newStack.top()) {
            newStack.push(value);
        } else {
            while (!newStack.isEmpty() && newStack.top() > value)
                stack.push(newStack.pop());
            newStack.push(value);
        }
    }
    while (!newStack.isEmpty())
        stack.push(newStack.pop());
}
public static void main(String args[]) {

    Stack<Integer> stack = new Stack<Integer>(7);
    stack.push(2);
    stack.push(97);
    stack.push(4);
    stack.push(42);
    stack.push(12);
    stack.push(60);
    stack.push(23);
    sortStack(stack);
    while(!stack.isEmpty()){
        System.out.println(stack.pop());
    }
}

​

​

} else {
            while (!newStack.isEmpty() && newStack.top() > value)
                stack.push(newStack.pop());
            newStack.push(value);

​大于原始堆栈，我们将值从新堆栈推向原始堆栈，然后将值推回新的堆栈？ 我在这里完全迷失了！有人可以帮我解释这部分吗？谢谢你！！！

Answer 1

该代码只需要其他部分，并且如果有很多重复值，则更简单的版本更快。我没有找到任何数据模式，这些数据模式比问题中的代码慢得多。

    public static void sortStack(Stack<Integer> stack) {
        Stack<Integer> newStack = new Stack<>();
        Integer value;
        while (!stack.isEmpty()) {
            value = stack.pop();
            while (!newStack.isEmpty() && newStack.peek() > value)
               stack.push(newStack.pop());
            newStack.push(value);
        }
        while (!newStack.isEmpty())
            stack.push(newStack.pop());
    }

链接到带有解释的C ++示例。

如果使用两个临时堆栈，则可以使用多相合并排序从O（n^2）降低到O（n^2）到O（n log（n）），但代码很复杂。