Dutch national flag problem

这个题目：separate negative and positive numbers while being stable，也就是给定一个长n数组，空间复杂度为O(1)，时间为O（n）, 重新排列，使得负数在前半部分，正数在后半部分，且不改变相对顺序；此题有许多变种，比如偶数奇数，在july的博客上多有讨论，自己一直对此有疑问，在stackoverflow上看到一个帖子：

 

How to sort an integer array into negative, zero, positive part without changing relative position?

 

templatetypedef回答：

This is an instance of the Dutch national flag problem studied by Edsger Dijkstra. It's interesting in that no stable solution to this problem is known that runs in O(n) time and O(1) space (or at least, the last time I checked the literature, no known solution to the problem exists).

 

Dijkstra大牛研究过，所以此题无解吗？