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

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

这是Edsger Dijkstra研究的荷兰国旗问题的一个例子.它的有趣之没有稳定解决这个问题众所周知,在O(n)的时间和O(1)空间(或至少,在我最后一次检查的文献,没有已知的问题的解决存在)上运行.

Answer 2

难道不能简单地使用仅检查符号的自定义比较器执行的任何“稳定排序”来完成此操作吗？

编辑：
不，那是 O(n log n)。

在线性时间内你可以做的一件事就是减少问题。由于零无法排序（如何区分一个和另一个？），因此您可以遍历数组，跳过零并用非零值填充。然后在末尾添加正确数量的零。

j=0;
for (i=0;i<N;i++) {
  if (A[i]) {
     A[j++]=A[i];
  }
}
while (j<N) {
   A[j++]=0;
}

现在你可以忽略最后一部分，问题就变成了为 0 附近的稳定分区找到一个 O(n) 算法。不幸的是，c++ stl 中的stable_partition函数只有 O(n) 比较，但是 O(n log n) 交换如果没有额外的可用空间。

然而，这篇文章：“Stable Minimum Space Partitioning in Linear Time”似乎表明在 O(n) 内是可能的。我想我对它的理解还不够清楚，无法在这里清楚地总结它。

如果可行，最后一步是将零插入分区之间，这也是 O(n)，因为零没有需要维护的顺序。