P*******b
发帖数: 1001 | |
r****o
发帖数: 1950 | 2 为啥一定要recursion呢？这题时间复杂度和空间复杂度有什么要求?
【在 P*******b 的大作中提到】
: 怎么ｒｅｃｕｒｓｉｏｎ？
|
P*******b
发帖数: 1001 | 3 就是要求不要ｅｘｔｒａ的ｓｔａｃｋ
【在 r****o 的大作中提到】
: 为啥一定要recursion呢？这题时间复杂度和空间复杂度有什么要求?
|
j**l
发帖数: 2911 | |
f*********5
发帖数: 576 | 5 这样可以不？
void sort(stack &st)
{
if (st.IsEmpty())return;
int temp=st.top();
st.pop();
sort(st);
Insert(st,temp); //insert temp to the right position in st
//here we can use a list to temporarily store
//the nodes whose value less than temp
}
【在 P*******b 的大作中提到】
: 怎么ｒｅｃｕｒｓｉｏｎ？
|
K******g
发帖数: 1870 | 6 感觉你这个仍然是在insert 排序，O（N^2）。那recursive有什么必要呢
直接挨个pop，insert不就好了？
【在 f*********5 的大作中提到】
: 这样可以不？
: void sort(stack &st)
: {
: if (st.IsEmpty())return;
: int temp=st.top();
: st.pop();
: sort(st);
: Insert(st,temp); //insert temp to the right position in st
: //here we can use a list to temporarily store
: //the nodes whose value less than temp
|
y*c
发帖数: 904 | 7
这个是对的，然后在写一个recursive的insert, which maintains order. The
structure is similar to this sort.
【在 f*********5 的大作中提到】
: 这样可以不？
: void sort(stack &st)
: {
: if (st.IsEmpty())return;
: int temp=st.top();
: st.pop();
: sort(st);
: Insert(st,temp); //insert temp to the right position in st
: //here we can use a list to temporarily store
: //the nodes whose value less than temp
|
f*********5
发帖数: 576 | 8 wait
st已经是排序的了
insert不需要递归了，pop出小于temp的，然后插入temp，插入那些小于的，就OK
【在 y*c 的大作中提到】
:
: 这个是对的，然后在写一个recursive的insert, which maintains order. The
: structure is similar to this sort.
|
y*c
发帖数: 904 | 9
That's right. 不过一般需要system stack (recursion), 不是另外搞一个stack。
【在 f*********5 的大作中提到】
: wait
: st已经是排序的了
: insert不需要递归了，pop出小于temp的，然后插入temp，插入那些小于的，就OK
|
