稳定排序问题，要求O(n)时间，O(1)空间

问题：

微软： 给定一个 Integer Array，只有正数和负数。使让所有正数排在所有负数后面，所有正数间相对位置不变，所有负数间相对位置不变。要求 In-Place，空间复杂度 O(1)。

Facebook：一个记录数组，每个记录的关键字是0，1，2三个数中的一种，要求将数组按关键字排序。要求算法是稳定排序，O(n)时间，常数空间。

Amazon：一个数组，包含positive，negative, zero 三种数，要求按照 positive，zero, negative 排序，而且不能改变原记录的相对次序，O(1)空间。

以Facebook为例，解题思路：by swanswan @ mitbbs

第一遍：count0，1，2的个数l, m, n
第二遍：根据l,m,n很容易确定每个元素最终要挪到哪个位置，把数组元素值改成最终
目的地的下标
第三遍：根据a[i]!=i的条件进行swap到最终位置
第四遍：根据l,m,n恢复数组元素值为0,1,2

参考代码：

Data a[size];
...
int l=0,m=0;
for (int i=0; i seems true, but no proof yet // by mitkook
   while (a[i].key!=i) {
      int swapIdx = a[i].key;  // modified by me -> mitkook
      Data tmp = a[swapIdx];
      a[swapIdx] = a[i];
      a[i] = tmp;
   }
}
for (int i=0; i

如果是关键字是正数、0、负数，按照 >0, =0, <0 进行分，感觉就不行了，最后没法恢复。

参考资料：

http://en.wikipedia.org/wiki/Dutch_national_flag_problem

http://www.mitbbs.com/article_t1/JobHunting/32070945_0_2.html