按顺序排列正负数的数组

Question

这是一道面试题，我被卡住了。

问题：给定一个包含正数和负数的整数数组，需要将正数移到一侧，将负数移到另一侧，并保持原有顺序。例如，{-1,5,3,-8,4,-6,9} 变为 {-1,-8,-6,5,3,4,9}。要求时间复杂度为 O(n)，且不能使用额外的数组。

首先，我考虑使用快速排序来解决此问题，伪代码如下：

找到距离零最近的元素作为枢轴元素，然后对数组应用一次快速排序，这样可以在 O(n) 的时间内完成。

但是，快速排序不是稳定排序算法。

之后，我想出了以下解决方案。

伪代码如下：

初始时，将 current 递增到第一个正数，将 end 递减到最后一个负数。

如果当前元素为负数，将其加1。 如果当前元素为正数，将其与末尾位置的元素交换，同时将当前位置和末尾位置均减1。 如果当前位置大于等于末尾位置，则结束循环。

仍未得到正确答案。需要对此提出建议。

- Sharad

---

这不是一个解决方案，而是一个提示：复杂度限制（O(n)，也称为“线性”）是一个很大的提示。你不能使用快速排序，因为它平均需要nlog(n)时间，并且在最坏情况下是二次的。实际上，你不能使用任何具有类似要求的比较元素的算法，因为它们都至少具有nlog(n)的复杂度。你必须在不将所有元素相互比较的情况下对它们进行排序。[顺便说一句，当我说“log”时，它是以2为底的对数。] - Kevin Grant

我可能错了，但也许他们只是想看看你如何解决问题，而不是得到一个实际的解决方案？基数排序 最接近，但我认为没有同时在原地和稳定的实现。它也只对只有一位数字的数字数组是O(n)的。尽管如此，仍然相当不错。 - nbrooks

相关：哪个算法可以使用仅O（N）次移动进行稳定的原地二进制分区？。 - Jesse Good

@Jesse：我认为这不仅仅是相关的，而且是重复的。或者你看到了区别吗？ - Ben Voigt

@itsols：我认为插入排序不能同时保证原地排序和稳定性。 - Matthieu M.

Answer 1

std::stable_partition 正好符合您的需求。

对于 C++11，请执行以下操作

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

- David Norman

---

有趣。你知道这种方法背后使用了什么样的算法吗？在整数上进行O(n)、原地和稳定排序听起来很棘手。 - nbrooks

复杂度：最多(last - first) * log(last - first)次交换，但如果有足够的额外内存，则只需要线性数量的交换。精确地说，谓词将被应用last - first次。 - Ben Voigt

在最坏情况下，时间复杂度为n log n，且不是原地排序。 - nbrooks

@nbrooks: 要么是O(n)，要么就是原地操作，但两者不可兼得。 - Ben Voigt

@ben 一般来说，如果你不能保证它在特定时间内是这样的，那么你就不能真正将算法归类为那种类型，但我接受你关于语言注释的观点。 - nbrooks

@nbrooks：显然有两种算法，每种都提供不同的保证。使用哪种取决于是否成功分配一个相等大小的第二个数组。 - Ben Voigt

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)的解决方案，又不需要分配额外数组的方法。

- Brian L