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

Give you an array which has n integers,it has both positive and negative integers.Now you need sort this array in a special way.After that,the negative integers should in the front,and the positive integers should in the back.Also the relative position should not be changed.
eg. -1 1 3 -2 2 ans: -1 -2 1 3 2.
o(n)time complexity and o(1) space complexity is required.

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

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

Quicksort的一次partition。。

恩。partition的时候，记得不要把order变乱。所以是stable的quicksort的一次partition。

xutopia 发表于 2013-9-5 11:01
Quicksort的一次partition。。

quick sort 是nlogn如何破

AriosMaclaine 发表于 2013-9-5 09:59
quick sort 是nlogn如何破

不是整个quicksort，只是其中的一次partition。
比如leetcode里面和这个版里面都提到过一个题：给一个里面只有三种元素：0，1，2的数组排序，一个道理。

这个题目，我只想到一个O(nlogn)的算法，因为要保证相对顺序，是变形的快排。但不是O(n).

和0，1，2的排序不一样吧，0，1，2有几种方法，三个指针或者变形的计数统计。

在网上找了一下，这个问题属于stable 0-1 sorting的问题，有一篇论文：http://www.diku.dk/hjemmesider/ansatte/jyrki/Paper/KP92b.pdf

采用的一种块排序的方法。

楼上能详细说下O(n)的快排变形么？没想明白，thx

sing1ee 发表于 2013-9-5 09:36
这个题目，我只想到一个O(nlogn)的算法，因为要保证相对顺序，是变形的快排。但不是O(n).

和0，1，2的排 ...

partition是n， 快排是n log n .

没注意stable。 要stable么， 我不清楚有没有stable的 partition， 应该有吧。

有个简单的方法， 用两个指针， 扫描该数组， 负数以此加入负数指针队尾， 正数加入正数指针队尾.

然后俩指针前后拼一块， 算法只需要维护头指针和尾指针就行，但是内存里开辟了别的地址存储值。  这算不算O（1）空间复杂度？

sing1ee 发表于 2013-9-5 10:36
这个题目，我只想到一个O(nlogn)的算法，因为要保证相对顺序，是变形的快排。但不是O(n).

和0，1，2的排 ...

哦对，是我想错了。一开始没注意stable......
stable的话，inplace至多应该是时间复杂度O(nlogn)的方法了吧，采用的是merge sort的东西（跟你说的块排序不知道是不是一样？）

非得要O(n)的话，估计就得跟农民那种似的，整个linkedlist或者vector啥的来分，但是那样空间就肯定不是O(1)了
我觉得可能非要要求时间复杂度O(n)空间复杂度O(1)，应该没有- -

这题应该没有方法能同时满足时间和空间的条件。。。