arrays - 如何在不改变相对位置的情况下将整数数组排序为负数、零、正数部分？

Question

给出一个复杂度为 O(n) 的算法，该算法将数组 S 作为输入，然后将 S 分成三组:负数、零和正数。展示如何就地实现它，即不分配新内存。而且你必须保持数字的相对顺序。 例如: {-1, 4, 0, -2, 1, 2} ==> {-1, -2, 0, 4, 1, 2}

我不确定是否存在这样的解决方案。我能想到的最佳解决方案是:

解决方案 1:使用额外的整数数组，然后遍历整个数组以获得负数，然后是 0，然后是正数。

解决方案 2:不保留数字的相对顺序。然后循环数组两次:

    template <typename Type>  
void Partion(Type *array, int begin, int end, Type v, int &l, int &r) 
{  
    l = begin;  
    for (int i=begin; i!=end; ++i)  
    {  
        if (array[i] < v)  
            swap(array[i], array[l++]);  
    }  
    r = l;  
    for (int j=l; j!=end; ++j)  
    {  
        if (array[j] == v)  
            swap(array[j], array[r++]);  
    }  
} 

Answer 1

这是 Dutch national flag problem 的一个实例由 Edsger Dijkstra 研究。有趣的是，这个问题的稳定解决方案是已知的，在 O(n) 时间和 O(1) 空间内运行(或者至少，我上次检查文献时，没有已知的解决方案问题存在)。