如何将整数数组按负数、零、正数部分排序，而不改变它们之间的相对位置？

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++]);  
    }  
} 

- Gin

---

三个循环怎么样，每个集合一个，每次遇到集合的成员时进行冒泡交换？ - mmr

你是在将数组分成三个集合（负数、零、正数），同时保持每个集合中数字的相对位置不变吗？我问这个问题是因为你给出的例子似乎自相矛盾 - {-1, 4, 0, -2, 1, 2} ==> {-1, -2, 0, 1, 2, 4}。如果项目确实是排序的，那么-2应该在-1之前，而如果它们被分组为(-,0,+)并且保持每个组内数字的相对位置不变，那么结果应该是{-1, -2, 0, 4, 1, 2}，其中4出现在1和2之前。 - Anurag

@Anurag 谢谢你的通知。我已经修复了。 - Gin

@mmr，我的观点不是关于通过的次数，而是简单交换无法保留序列。例如：{1 -2 0 2 0 3 -1}；第一次交换 => {-2 -1 0 2 0 3 1}；第二次交换 => {-2 -1 0 0 2 3 1}。如果你改用“冒泡交换”，那么时间复杂度又回到了N lg N。 - AShelly

假定保持“相对顺序” 对于零值集合没有影响，这种假设是否有效？如果它们被交换，会有什么影响吗？0 == 0 == 0。 - AShelly

Answer 1

这是艾兹赫·迪科斯彻研究的荷兰国旗问题的一个实例。有趣的是，目前尚未找到任何稳定的解决方案，可以在O(n)时间和O(1)空间内运行（或者至少在我上次查阅文献时，没有已知的解决方案存在）。

- templatetypedef

---

一个O(n)时间和O(n)空间复杂度的解法是直接的。 - James McNellis

@James McNellis- 是的，但是OP问如何原地完成此操作（我认为这意味着O(1)内存）。 - templatetypedef

是的，那就是我的假设。 - James McNellis

我认为这不完全是荷兰国旗问题。在那个问题中，没有任何元素可以移动超过一次，并且每个类的元素是无法区分的（没有稳定性要求）。目前的问题允许元素最多移动O(1)次，但必须以稳定的方式对元素进行分区。 - Ted Hopp

这是稳定三元分区的DNF问题的变体。你说得对，它并不完全适合，但我的观点仍然成立，即这个问题尚未解决。感谢你指出这一点。 - templatetypedef

Answer 2

我不确定这是否有帮助，但将稳定地分成三类的要求简化为稳定地分成两类的问题：将负数与非负数分开，然后将正数与非正数分开。如果可以在O（1）空间和O（n）时间内解决两类问题，则可以将解决方案应用两次以解决原始问题。

- Ted Hopp

Answer 3

零可以互换，所以我假设您不关心它们是否被交换或者在最后甚至被简单地覆盖（即，在我们完成将正数和负数移到数组的两端之后，我们只需将中间部分归零）。

如果您正在处理整数仅作为其他更大东西的键的情况，则可能不是这种情况-您可能希望保留零并进行稳定的分区。但如果没有，这里有两个见解：

首先，您的问题与稳定二进制分区问题相同。

当然，您的问题算法会进行稳定的二进制分区（只是一个没有零的数组）。相反，如果数组有零，您仍然可以使用二进制分区来完成脏工作：从右到左扫描整个数组，每次遇到一个零就与下一个负值进行交换（跟踪其位置，以便您不会总共扫描n^2），结果为

[mixed -,+][possibly extra zeros][mixed 0,+].

然后，您可以进行两个二进制分区，以获得

[-][+][0][+]

并将+值移动到所需的结果。

据我所知，使用二进制分区，您可以选择任意两个稳定的、原地的和O(n)的算法。所以看起来你运气不好，但显然已知有一种原地O(n*log n)的算法，还有一种使用log(n)临时空间的O(n)算法。

其次，如果你能保证零的数量至少为f(n)，那么零可以弥补临时空间的不足；只需按以下步骤执行，即可在O(n^2/f(n))的时间内获得一个稳定的原地分区。特别是，如果零至少占数组的某个常数分数，通过重复以下两个步骤直到完成，您可以获得O(n)的运行时间：

1. 从右向左扫描数组，在遇到的每个零与下一个负值交换。 2. 从左向右扫描数组，在遇到的每个零与下一个正值交换。

如果零的数量与其他类型的元素一样多，那么在执行1、2、1这三个步骤后就完成了。

- Prodicus

---

你能否请提供一些参考资料来支持你的陈述？ - gen

Answer 4

使用自定义比较器执行任何“稳定排序”并仅检查符号，这样做不简单吗？

编辑：
不，那是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)算法。不幸的是，stable_partition函数来自c++ stl只有O(n)比较，但如果没有额外的空间，则需要O(n log n)交换。

然而，这篇文章："Stable minimum space partitioning in linear time"似乎表明它可以在O(n)中实现。我认为我还没有足够清楚地总结它。

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

- AShelly

Answer 5

C++库中有一个stable_partition算法，它在原地运行时需要n次比较和O(n log n)次交换。

正如@Ted 指出的那样，这个问题需要两次应用这个算法。

- aaz