如何在不改变相对位置的情况下，将一个整数数组排序为负的、零的、正的部分?

Give an O(n) algorithm which takes as input an array S, then divides S into three sets: negatives, zeros, and positives. Show how to implement this in place, that is, without allocating new memory. And you have to keep the number's relative sequence. for example: {-1, 4, 0, -2, 1, 2} ==> {-1, -2, 0, 4, 1, 2}

给出一个O(n)算法，它以一个数组S作为输入，然后将S分为三个集合:负数、零和正数。演示如何在不分配新内存的情况下实现这一点。你必须保持数字的相对顺序。例如:{ 1 4 0、2、1,2 } = = > { 1 2 0、4、1、2 }

I am not sure whether or not such an solution exits. The best solutions I can think out are:

我不确定这种解决方案是否存在。我能想到的最好的解决办法是:

Solution 1: Using an extra integer array, then traverse the whole array to get negatives, then 0s, then positives.

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

Solution 2: Do not keep number's relative sequence. Then loop the array two times:

解决方案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++]);  
    }  
}

5 个解决方案

#1

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).

这是Edsger Dijkstra研究的荷兰国旗问题的一个例子。有趣的是，这个问题的稳定解在O(n)时间和O(1)空间中都不存在(至少，我上次查阅文献时，没有已知解存在)。

#2

I'm not sure if this helps, but the requirement to stably partition into three classes can be reduced to the problem of stably partitioning into two classes: separate the negative from non-negative, then the positive from non-positive. If the two-class problem can be solved in O(1) space and O(n) time, the solution can be applied twice to solve the original problem.

我不确定这是否有帮助，但是稳定地划分成三个类的要求可以归结为两个类的稳定划分问题:将负的和非负的区分开来，然后从非正的变为正的。如果可以在O(1)空间和O(n)时间内解决这两个类问题，那么这个解可以应用两次来解决原始问题。

#3

Zeros are indistinguishable so I presume you don't care whether they get swapped around or even simply overwritten at the end (i.e. we just zero out the middle part after we've finished getting the positive and negative numbers moved to opposite ends of the array).

0是不可区分的，所以我假设你不关心它们是否交换了，或者仅仅是在最后被覆盖了(例如，当我们把正的和负的数字移到数组的两端后，我们就把中间的部分变成了0)。

If you're looking at a situation where the integers are just keys for something bigger, this may well not be the case- you may want zeros preserved and stably partitioned. But if not, here's two insights:

如果你看到的情况是，整数只是更大的东西的键，那么情况很可能不是这样——你可能希望保留0并稳定地分区。但如果不是，这里有两个洞见:

First, your problem is identical to the stable binary partition problem.

首先，你的问题和稳定的二元分割问题是一样的。

An algorithm for your problem of course does stable binary partitions (just an array with no zeros). Contrariwise, if the array has zeros you can still use a binary partition to do the dirty work: scan right through the array, swapping each zero you come across with the next negative value (keeping track of where that was so you don't do n^2 overall scanning), resulting in

一个解决问题的算法当然可以实现稳定的二进制分区(只是一个没有零的数组)。相反,如果数组0你仍然可以使用二进制分区做肮脏的工作:扫描穿过数组,交换每个零你遇到下一个负值(跟踪,所以你不要做n ^ 2整体扫描),导致

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

[混合，+][可能额外的零][混合0，+]。

Then you do two binary partitions to get

然后执行两个二进制分区

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

and shift the + values over to get the desired result.

并将+值转换为期望的结果。

AFAIK with binary partitions you can choose any two of stable, in-place, and O(n). So it looks like you're outta luck, but apparently an in-place O(n*log n) algorithm is known as is an O(n) algorithm using log(n) scratch space.

有二进制分区的AFAIK可以选择任何两个稳定的、就地的和O(n)。看起来你是幸运的，但是显然，一个in-place O(n*log n)算法是一个O(n)算法，它使用log(n) scratch空间。

Second, if you can guarantee that the number of zeros will be at least f(n), the zeros can compensate for the lack of scratch space; it's simple to get a stable in-place partition in time O(n^2/f(n)). In particular, if the zeros will be at least some constant fraction of the array, you get O(n) runtime by just running these two steps till you're done:

第二，如果你能保证0的个数至少是f(n)，那么0就可以弥补零空间的不足;很容易得到一个稳定的就地分区及时O(n ^ 2 / f(n))。特别是，如果0至少是数组的常数部分，你只需要运行这两个步骤就可以得到O(n)运行时间，直到你完成:

Scan right through the array, swapping each zero you come across with the next negative value
扫描整个数组，交换你遇到的每一个0，得到下一个负值
Scan left through the array, swapping each zero you come across with the next positive value
扫描整个数组，将遇到的每个0替换为下一个正值

If zeros are just as plentiful as either of the other types, this is done after doing 1 then 2 then 1 again.

如果0和其他任何一种都一样多，这是在做1之后再做2然后再做1。

#4

Can't this be done simply using any "stable sort" performed with a custom comparitor which only checks the sign?

这难道不能简单地使用任何“稳定排序”来完成吗?

Edit:
No, that's O(n log n).

编辑:不，是O(n log n)

One thing you can do in linear time is reduce the problem. Since the zeros can't be ordered (how do you tell one from the other?), you can make a pass where you walk through the array, skipping the zeroes and filling in with the non-zero values. Then add the correct number of zeros at the end.

线性时间可以做的一件事就是减少问题。由于0不能被排序(如何区分它们?)，您可以在遍历数组的地方创建一个pass，跳过0并填充非零值。然后在末尾添加正确的0。

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

Now you can ignore the last section and the problem becomes finding an O(n) algorithm for a stable partition around 0. Unfortunately, the stable_partition function from the c++ stl has only O(n) comparisons, but O(n log n) swaps if no additional space is available.

现在可以忽略上一节，问题是在0附近找到一个稳定分区的O(n)算法。不幸的是，c++ stl中的stable_partition函数只有O(n)比较，但是如果没有其他可用空间，那么O(n log n)会交换。

However, this article: "Stable minimum space partitioning in linear time" seems to indicate that it is possible in O(n). I don't think I understand it well enough to summarize it clearly here.

然而，这篇文章:“线性时间内稳定的最小空间划分”似乎表明在O(n)中是可能的。我不认为我理解得足够清楚，不能在这里把它总结得很清楚。

If that works, The final step is to insert the zeros back inbetween the partitions, which is also O(n), since the zeros have no order to maintain.

如果这样做，最后的步骤是在分区之间插入0，也就是O(n)，因为0没有维护的顺序。

#5

The C++ library has a stable_partition algorithm which requires n comparisons and O(n log n) swaps when it runs in-place.

c++库有一个stable_partition算法，它需要n个比较和O(n log n)交换。

As @Ted points out, the problem requires two applications of this algorithm.

正如@Ted所指出的，这个问题需要两个应用程序。

#1

#2

#3