找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 1234|回复: 4
收起左侧

[资源分享] 13: Sort A Stack

[复制链接]

19

主题

2

精华

83

积分

资深会员

Rank: 2

积分
83
发表于 10-3-2015 01:37 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
用一个辅助栈存放单调的序列,栈顶->栈底递减,当发现原栈栈顶>辅助栈栈顶时,先取出这个数,再将辅助栈中的数依次压入原栈,直到辅助栈的栈顶元素不小于这个数,实际是类似插入排序的思想,复杂度也是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. };
复制代码


14

主题

1

精华

321

积分

高级会员

Rank: 3Rank: 3

积分
321
发表于 10-6-2015 05:50 AM | 显示全部楼层
同样的思路,可以模仿非递归的MergeSort,复杂度降到O(nlgn)
回复 支持 反对

使用道具 举报

19

主题

2

精华

83

积分

资深会员

Rank: 2

积分
83
 楼主| 发表于 10-6-2015 06:58 AM | 显示全部楼层
daisy8867 发表于 10-6-2015 05:50 AM
同样的思路,可以模仿非递归的MergeSort,复杂度降到O(nlgn)

可不可以给个代码看看呀
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表