13: Sort A Stack

uuuouou

用一个辅助栈存放单调的序列，栈顶->栈底递减，当发现原栈栈顶>辅助栈栈顶时，先取出这个数，再将辅助栈中的数依次压入原栈，直到辅助栈的栈顶元素不小于这个数，实际是类似插入排序的思想，复杂度也是O(N^2)的

1. class Solution {
   
2. public:
   
3.         stack<int> sortStack(stack<int> &s) {
   
4.                 if(s.size() < 2) return s;
   
5.                
   
6.                 stack<int> t;
   
7.                 while(true){
   
8.                         do{
   
9.                                 t.push(s.top()); s.pop();
   
10.                         }while(!s.empty() && s.top() <= t.top());
    
11.                         if(s.empty()) break;
    
12.                        
    
13.                         int tmp = s.top(); s.pop();
    
14.                         while(!t.empty() && t.top() < tmp){
    
15.                                 s.push(t.top()); t.pop();
    
16.                         }
    
17.                         t.push(tmp);
    
18.                 }
    
19.                 while(!t.empty()){
    
20.                         s.push(t.top()); t.pop();
    
21.                 }
    
22.                 return s;
    
23.         }
    
24. };

复制代码

daisy8867

同样的思路，可以模仿非递归的MergeSort，复杂度降到O(nlgn)

uuuouou

daisy8867 发表于 10-6-2015 05:50 AM
同样的思路，可以模仿非递归的MergeSort，复杂度降到O(nlgn)

可不可以给个代码看看呀