关于划分，大家在讨论快排时已经说得比较多了，这里我主要说说如何在空间复杂度为O(1)的情况下进行稳定的划分。

首先看两道面试题：

百度面试题（一）：假设一整型数组存在若干正数和负数，现在通过某种算法使得该数组的所有负数在正数的左边，且保证负数和正数间元素相对位置不变。时空复杂度要求分别为：o(n)和o(1)。

百度面试题（二），给定一个存放正数的数组，重新排列数组使得数组左边为奇数，右边为偶数，且保证奇数和偶数之间元素相对位置不变。时空复杂度要求分别为：o(n)和o(1)。

这两道题是搜面试题时从这里找到的，说老实话，里面的答案真是不够靠谱的……

这两题的本质就是划分，划分条件分别是为负数和为奇数，另外附加有稳定和无额外空间需求的条件，C++里直接用std::stable_partition做就好。

不过有一个小小的陷阱，C++标准里并没有规定std::stable_partition的空间复杂度，而且std::stable_partition实际上需要的空间确实为O(n)。下面说一下如何实现无需额外空间的inplace stable partition。

我采用分而治之的方式来进行处理，把数据劈成两半，两边分别进行递归处理，这时我们可以确定两边都已经划分完毕，以第二题为例，那么我们得到了|正数1|负数2|正数3|负数4|的排列，只需要把中间的两端交换一下就可以了，变为|正数1|正数3|负数2|负数4|。

细节问题：

1. 相邻区间交换可以用std::rotate，时间复杂度为O(n)
2. partition函数需返回划分处，要注意rotate之后划分处的计算
3. 对于只有一个数的情况想想什么才是正确的返回值

下面是第二题的范例代码，出于演示的目的就没有做成通用型的了。

#include <stdio.h>
#include <algorithm>
using std::rotate;

bool predicate(int i)
{
    return i > 0;
}

int inplace_stable_partition(int *a, int i, int n)
{
    if (i == n - 1)
        return predicate(a[i]) ? i + 1 : i;

    int middle = i + (n - i) / 2;
    i = inplace_stable_partition(a, i, middle);
    n = inplace_stable_partition(a, middle, n);

    rotate(a + i, a + middle, a + n);
    return i + n - middle;
}

int main(int argc, char *argv[])
{
    int a[] = { 1, -1, 2, -2, 3, -3 };
    inplace_stable_partition(a, 0, 6);
    for (int i = 0; i < 6; i++)
        printf("%d ", a[i]);
    
    return 0;
}