Google: O(n) and O(1) in resorting an array

北美农民 发表于 2013-9-5 22:49
partition是n， 快排是n log n .

只是partition不保序的，还需要进一步处理呀

yxyxyx 发表于 2013-9-5 23:24
哦对，是我想错了。一开始没注意stable......
stable的话，inplace至多应该是时间复杂度O(nlogn)的方法了 ...

看我推荐的论文，方法很复杂，但是有的。
我觉得，只要掌握了nlogn的方法就够了。

block sorting和merge sort有点类似吧，太复杂，我也没细看

快排的partition好像无法保持原来的相对位置,如果可以有人可以说下怎么做吗？

典型的3 color sort, 我面fb的时候也被问道了，一共就7，8行代码

csgtc 发表于 2013-10-23 12:22
典型的3 color sort, 我面fb的时候也被问道了，一共就7，8行代码

3 color sort 但是这个partition后positive integer顺序会乱掉吧

baojialiang 发表于 2013-11-1 08:35
3 color sort 但是这个partition后positive integer顺序会乱掉吧

没注意到要stable...

用一个记录负值的指针和一个记录正值的指针不就可以了么。。

3 color 问题。3个指针。划分四个区域，0，1，2，和未知区域。

同求答案。。。。

这个有人做出来了没有
我被折磨死了，这题目，我就要拿去问算法老师了。。。
我崩溃了。。。