P*******b 发帖数: 1001 | |
r****o 发帖数: 1950 | 2 为啥一定要recursion呢?这题时间复杂度和空间复杂度有什么要求?
【在 P*******b 的大作中提到】 : 怎么recursion?
|
P*******b 发帖数: 1001 | 3 就是要求不要extra的stack
【在 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 的大作中提到】 : 怎么recursion?
|
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
|