递归实现无额外空间栈排序：代码逻辑正确但输出异常求排查

嘿，我一眼就发现你代码里的关键问题了！你的递归逻辑思路完全没问题，但参数传递方式搞错了，导致所有修改都白做了，这才出现“输出完全随机”的假象——其实原栈根本没被排序！

核心错误：传值而非传引用 #

你现在的函数参数是stack<int> s，这是传值传递。C++里传值会创建一个参数的副本，你在递归函数里对栈做的push、pop操作，全都是在这个临时副本上进行的，原栈自始至终一点变化都没有！递归结束后，原栈还是最初的状态，看起来结果随机，其实只是原栈没被修改而已。

修复方案：改用传引用 #

只需要把两个函数的栈参数改成引用传递，也就是stack<int>& s，这样函数操作的就是原栈本身，所有修改都会生效。

修改后的完整代码 #

#include <stack>
using namespace std;

void insertatsortstack(int element, stack<int>& s) {
    if (s.empty() || element > s.top()) {
        s.push(element);
        return;
    }
    int temp = s.top();
    s.pop();
    insertatsortstack(element, s);
    s.push(temp);
}

void sortstack(stack<int>& s) {
    if (s.size() > 0) {
        int element = s.top();
        s.pop();
        sortstack(s);
        insertatsortstack(element, s);
    }
}

验证逻辑 #

修改后，递归流程就能正确作用于原栈了：

• sortstack会不断弹出栈顶元素，递归排序剩余的栈，直到栈为空；
• 然后把弹出的元素通过insertatsortstack插入到已排序的栈的正确位置（比栈顶大就直接入栈，否则弹出栈顶继续找位置，最后把弹出的元素放回）；
• 整个过程不需要额外空间（递归调用栈不算额外空间的话），完全符合你的需求。

内容的提问来源于stack exchange，提问作者user46562