l******g
发帖数: 188 | 1 sorting with 3 stacks.
all numbers are initially in stack one.
no other space allowed.
回答了一个O(N^2)的方法, 要问一个更小的. |
u*a
发帖数: 247 | 2 It's basically a merge sort. O(nlogn).
【在 l******g 的大作中提到】
: sorting with 3 stacks.
: all numbers are initially in stack one.
: no other space allowed.
: 回答了一个O(N^2)的方法, 要问一个更小的.
|
z***b
发帖数: 127 | 3 这个怎么用三个stack 实现merge sort?
【在 u*a 的大作中提到】
: It's basically a merge sort. O(nlogn).
|
F********y
发帖数: 400 | 4 土木转行过来的新人，下面都是我的想法，有错莫喷：
第一次轮流pop1个到两个stack里，然后merge回1号stack，因为merge操作，1号里每两
个元素彼此sorted。
第二次轮流pop2个到两个stack里，然后merge，结果1号里每四个元素彼此sorted。
然后循环直到pop数超过n/2，然后最后一次merge回去就结束了。
【在 z***b 的大作中提到】
: 这个怎么用三个stack 实现merge sort?
|
u*a
发帖数: 247 | 5 Assume you have two sorted stacks, you can merge them into the third stack.
Now do it recursively.
【在 z***b 的大作中提到】
: 这个怎么用三个stack 实现merge sort?
|
