c++ - 排列 +ve 和 -ve 数字的数组，顺序不变

<分区>

Possible Duplicate:
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) 中完成并且没有额外的数组。

首先我想通过像这样的快速排序来做到这一点

伪代码

找到最接近零的元素。将其设为主元元素。然后对数组应用一次快速排序。这是 O(n) 。

唉!但是快速排序不是稳定排序？

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

伪代码:

最初，增加电流直到第一个 +ve 数字和减速结束直到最后一个 -ve 数字

如果电流为负，增加电流如果 current 为正，则将它与 end 处的元素交换并递减 current 并同时结束如果 current >= end ，则中断。

仍然没有得到正确答案。需要这方面的建议

最佳答案

std::stable_partition 完全符合您的要求。

对于 C++11，做

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

关于c++ - 排列 +ve 和 -ve 数字的数组，顺序不变，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/11337774/