题目：假设一整型数组存在若干正数和负数，现在通过某种算法使得该数组的所有负数在正数的左边，且保证负数和正数间元素相对位置不变。时空复杂度要求分别为：o(n)和o(1)。
大概就是要求stable_partition的实现，然而stl中stable_partition实现利用了额外的空间，不符合题目要求呢。
正常会有两种实现方法：
（一）用一个游标，从前往后遍历，第一次遇到负数则继续，遇到正数则记录并接着走，再遇到负数则与刚记录的正数互换，并将记录后移一位，这样遍历完成的时候移位也完成了。
（二）用两个游标，一个位于数组头，往后遍历，一个位于数组尾，往前遍历。前面的遇到负数后面的遇到正数组则继续；前面的遇到正数后面的遇到负数则互换，直到后面游标小于前面游标算完成。
但是都不满足稳定性的要求，毕竟快排是不稳定的排序。
那这题应该怎么做呢。再花o(n)时间，把后半部分不稳定的地方给找到再rotate？？感觉好蛋疼。
巴扎黑2017-04-17 15:00:20
/**
1.要確保原有次序，則只能順次移動或相鄰交換。
2.i從左向右遍歷，找出第一個偶數。
3.j從i+1開始往後找，直到找到第一個奇數。
4.將[i,...,j-1]的元素整體後移一位，最後將找到的奇數放入i位置，然後i++。
5.終止條件：j向後遍歷查找失敗。
*/
高洛峰2017-04-17 15:00:20
不要做交換，做拷貝就可以了. 因為要求時間複雜度為o(n).
假設數組為a,
1.先找到第一個整數，記好位置為i，然後找到後面遇到的第一個負數,位置為j, 保存a[j]到臨時變數裡，將a[i, j-1]區間的數拷貝給a[i+1, j], 臨時變數賦值給a[i]，
2.位置i存放的是找到的負數
3 .繼續從j+1開始，找到下一個負數，位置為k, a[k]保存到臨時變數, 拷貝a[i+1, k-1] 到a[i+2, k], 臨時變數賦值給a[i+1]
4.此時i+1存放的是剛找到的負數
5.繼續前面的過程
例:
初始[1, -1, 2, -2, 3, 4]
第一次拷貝，-1放在位置0 [-1, 1, 2, -2, 3 , 4]
第二次拷貝，-2放在位置1 [-1, -2, 1, 2, 3, 4]
後面沒找到其它負數，就結束了.
黄舟2017-04-17 15:00:20
每個數字期望被移到的位置是固定的，可預期的。透過模擬觀察發現，只要每次將對應的數字移到它期望的地方，之後繼續移動當前位置的值到期望位置。則真個移位最終其實是M個子串的循環移位。那關鍵就是如何知道每個點的期望移位位置。
第一遍遍歷得到正數、負數的各自的總個數P和N，因此可以知道分界點在哪裡。
第二遍遍歷負數區域裡的正數和負數個數PL和NL。
k1表示右邊的負數往左側移動過的個數。
k2表示右邊的正數移動過的個數。
k3表示左邊的負數移動過的個數。
k4表示左邊的正數移動過的個數。
i指向負數區域的起點，j指向正數區域的起點。
如果目前位置在左側（其實時在左側起點），如果是正數，則移動到右側的k4位置。 （位置都是0開始）。如果是負數，則移動到左側的k3位置。
如果目前位置再右。如果目前是正數，移到右側的第PL+k2位置；如果是負數，則移動到左側的NL+k1位置。
任何時候當移動的目標位置等於最初的起點位置後，當前循環移位結束。
下一步循環開始的起點在左邊的第一個正數位置，也就是k1+k3的位置。
舉例：
用o表示負數，用x表示正數。
原串為
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
x o o x x o x x o o o x x o x o
分界點在0,7
第一輪的移位模式為0->8->3->9->4->10->5->2->1->0
第一輪之後k1=3, k3=3, 則下一輪的起點從6開始。
第二輪的移位為6->11->13->6
第三輪的移位為7->12->14->15-7
結束。每個元素只移動過一次，所以時間複雜度為O(N)。
使用的空間是5個，空間複雜度為O(1)
----下述答案的時間複雜度是O(N^2)--更新後的答案在上面--
假設負數是o，正數是x。
從前往後遍歷，每次找到xx..xoo..o的子串，進行循環左移變為oo..oxx..x;
下一次從上一次的x開始計算新的xx..xoo..o子串模式來轉換。
每個字元最多被操作兩次，因此複雜度是O(N)。
剩下的就是如果將xx..xoo..o在O(L)的複雜度內完成oo.oxx..x的變化。假設模式串為x1x2x3x4o1o2o3, 範圍內兩次倒置，第一次將兩個子串分別反轉，得到x4x3x2x1o3o2o1，第二次整體倒置得到o1o2o3x1x2x3x4。完成。一共是2*L次。
綜上，時間複雜度O(N)，每個元素最多移動了4次.空間複雜度O(1)
