排列顺序完整的+ve和-ve数数组

Question

可能重复： which algorithm can do a stable in-place binary partition with only O(N) moves?

这是我被击中的面试问题之一。

问题：给出了一个正负整数数组，你需要把正数移到一边，负数移到另一边，顺序保持不变。例如。{-1,5,3，-8,4，-6,9}至{-1，-8，-6,5,3,4,9}。这应该在O(n)中完成，而不需要额外的数组。

首先，我想通过快速排序来做这件事

伪码

找到最接近zero.make的元素，它的支点是element.then，在array.this上应用一次快速排序是O(n)。

天哪！但是快速排序不是稳定排序吗？

在那之后，我提出了以下解决方案

伪码：

最初，增量电流到第一个+ve数，直到最后一个-ve数结束。

如果当前为负值，增量电流(如果当前为正)，则将其与结束和递减电流(如果当前为>=结束)的元素交换，然后断开。

还是没有得到正确的答案。需要对此提出建议

Answer 1

std::stable_partition做你想做的事。

对于C++11，请执行

std::stable_partition(
  array.begin(), array.end(),
  [] (int i) { return i < 0; });

Answer 2

如果结果数组与源数组不同，则可以在两次传递中轻松完成：

p = 0;   //current index in result array

For i = 0 to length - 1 :
    If source[i] < 0 then
        result[p] = source[i]
        increment p
    End if
End for

For i = 0 to length - 1 :
    If source[i] >= 0 then
        result[p] = source[i]
        increment p
    End if
End for

如果你想就地做的话，那就有点棘手了。您可以尝试一个冒泡类型的排序，但这是O(n^2)：

n = 0  // number of negative items found

For i = 0 to length - 1 :
    If array[i] < 0 then
        For j = i - 1 downto n :
            swap array[j+1] and array[j]
        End for

        increment n
    End if
End for

不幸的是，我想不出一个既为O(n)又不需要分配额外数组的解决方案。