顾名思义(?)类似于单调栈？维护一个单调递减的栈。一旦准备入栈的元素大于栈顶元素，栈一直弹出直到准备入栈的元素小于等于栈顶元素，弹出的元素压入另一个tmp栈中。
1 #include <iostream> 2 #include <stack> 3 #include <cstdlib> 4 #include <ctime> 5 using namespace std; 6 7 void StackSort(stack<int>& s) 8 { 9 stack<int> tmp; 10 while(!s.empty()){ 11 tmp.push(s.top()); 12 s.pop(); 13 } 14 while(!tmp.empty()){ 15 if(s.empty()){s.push(tmp.top());tmp.pop();} 16 else{ 17 int x=tmp.top(); 18 tmp.pop(); 19 if(x<=s.top()) s.push(x); 20 else{ 21 while(!s.empty()&&x>s.top()){ 22 tmp.push(s.top()); 23 s.pop(); 24 } 25 s.push(x); 26 } 27 } 28 } 29 } 30 31 void display(stack<int> s) 32 { while (!s.empty()) cout<<s.top()<<endl,s.pop(); 33 cout<<endl; 34 } 35 int main(int argc,char**argv) 36 { const int n{20}; 37 srand((unsigned)time(0)); 38 stack<int> s; 39 for (int i{0};i<n;i++) s.push(rand()%100); 40 cout<<"Before sorting:"<<endl<<endl; display(s); 41 cout<<"After sorting:"<<endl; StackSort(s); display(s); 42 return 0; 43 }
s：
tmp： 8 7 9
s: 9
tmp： 8 7
s: 9 7
tmp： 8
s: 9 8
tmp： 7
s: 9 8 7
tmp：