CCI题目:3-6:Stack Sort

By | 2012 年 11 月 20 日

其实是冒泡排序,两个stack来回倒腾。
代码展示的是比较直观的算法,对st排序,用另一个栈buffer作为辅助空间,那么:

1.逐个从st中pop元素,先pop到一个临时变量,如果pop出来的元素比临时变量小,则直接进入buffer,否则,把临时变量顶入buffer,st新pop到临时变量。
最后把临时变量push进buffer。
2.将buffer中的元素全部倒回st
3.重复1,2两步,直到1中第一种情况不出现为止。

《CCI》上的解法更效率一些(在阶上没有提升),就是在st到buffer中处理的过程中,允许中途将buffer中的元素倒回一部分到st,直到临时变量找到位置,然后继续将st向buffer倒。直到st为空。

此外,想到一个O(nlogn)的方法,就是,既然要用到额外最多s.size()的空间,还不如建一个最大值堆,把从stackpop出来的内容放到堆里面,然后将最大值逐个push回去。O(n logn),比参考答案快。



题目
Write a program to sort a stack in ascending order. You should not make any assump- tions about how the stack is implemented. The following are the only functions that should be used to write this program: push | pop | peek | isEmpty.
注:是允许用额外的Stack作为辅助空间的。



Code

<

pre>

//
// main.cpp
// CCI.3.6.Sort a Stack
//
// Created by Qiu Xiangyu on 12-11-20.
// Copyright (c) 2012年 Qiu Xiangyu. All rights reserved.
//

include

include

using namespace std;
void sortStack(stack &st) {
stack buffer;
bool bubble = true;
int rnd = 1;
while (bubble) {
cout<<“round “<<rnd++<<endl;
bubble = false;
//1.dump numbers from st to buffer and change the order of them
int middle = st.top();
st.pop();
while (st.size()) {
if (middle > st.top()) {
//if st.top is less than the one pop before, then pop to buffer
buffer.push(st.top());
bubble = true;
} else {
//if st.top is ge the one pop before, then push the middle to buffer ,then pop to middle
buffer.push(middle);
middle = st.top();
}
st.pop();
}
buffer.push(middle);
//2.dump buffer to st
while (buffer.size()) {
st.push(buffer.top());
buffer.pop();
}
}
}
int main(int argc, const char * argv[])
{
std::cout << “Hello, World!\n”;
stack st;
srand((unsigned int)clock());
for (int i = 0; i < 100; ++i) {
st.push(rand() % 10);
}
sortStack(st);
while (st.size()) {
cout<<st.top()<<endl;
st.pop();
}
return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注