顏色分類
給定一個包含紅色纽疟、白色和藍色，一共 n 個元素的數(shù)組憾赁，原地**對它們進行排序仰挣，使得相同顏色的元素相鄰，并按照紅色缠沈、白色膘壶、藍色順序排列。
此題中洲愤，我們使用整數(shù) 0颓芭、 1 和 2 分別表示紅色、白色和藍色柬赐。
示例:
輸入:** [2,0,2,1,1,0]
輸出: [0,0,1,1,2,2]</pre>
進階：
- 一個直觀的解決方案是使用計數(shù)排序的兩趟掃描算法亡问。
首先，迭代計算出0肛宋、1 和 2 元素的個數(shù)州藕，然后按照0、1酝陈、2的排序床玻，重寫當前數(shù)組。 - 你能想出一個僅使用常數(shù)空間的一趟掃描算法嗎沉帮？
題目分析
- 相同元素相鄰锈死，換句話說即分區(qū)存放，一個顏色一個區(qū)域穆壕，但因為這里顏色使用0 待牵，1，2表示喇勋，即對一個012的無序序列進行排序缨该，變成000...111....2222的順序。
正常排序算法都適用川背，只不過這里注意僅有三種可能的順序值贰拿，可以有特殊做法。
- 對于一個元素渗常，我們將他分區(qū)時壮不，肯定是插在區(qū)域的末尾，換句話說皱碘，我們只要保留每個區(qū)域的末尾下標询一，插入的時候交換過去就可以了。
三個區(qū)域，其實我們只要確定了兩個區(qū)域即可確定第三個區(qū)域健蕊，因為0區(qū)域在最左邊菱阵，2區(qū)域在最右邊，方便程序定位缩功，因此取0 2 的末尾指針保留下來晴及。
- 確定了雙指針確定區(qū)域，那么怎么進行遍歷處理呢嫡锌？確定了分類移動的位置虑稼，即cur遍歷每一位的數(shù)值，分類處理遇到0放左邊势木，遇到2放右邊蛛倦，02放好了，則1的區(qū)域也放好了啦桌。
針對cur的分類處理：
是0瀑凝，則和0的flag 输莺，left交換值薪寓，同時left++女蜈。此時cur獲取的是之前的left交換過來的值。我們知道我們換過去的處理好了板驳，那么這個換過來的還需要處理嗎又跛？目前還不知道，先看2的情況的處理笋庄。
是2效扫，則和2的flag，right交換直砂，同時right--。同樣浩习，此時cur獲取了交換過來的值静暂，由于這個值必然是在cur右邊（因為它是原right，即cur的右邊界）谱秽，則cur肯定沒有遍歷過這個值洽蛀。
同時因為它在cur右邊，它也不可能是交換過去的疟赊，因為交換過去的值肯定都在0 2 區(qū)域里了郊供。
因此這個值是野生的，所以cur在此停留近哟，繼續(xù)處理這個交換過來的值驮审。是1，因為我們把0 2 排序好，1的區(qū)域自然就出來了疯淫，因此1直接不處理地来，過就好了
-
那么看看0的情況交換過來的值？首先這個值的位置關(guān)系熙掺，即原left是在cur左邊還是右邊呢未斑？
只有當left會在cur右邊時，left指向的才可能是cur沒處理過的币绩，但此時cur在left內(nèi)部蜡秽？那cur就是把一個0換到了外邊，把一個亂序的換進了0的內(nèi)部缆镣，內(nèi)鬼毫無意義载城。
當left在cur左邊時，即left指向的必定經(jīng)過了cur的洗禮费就，而且它必不是原來在后面被換到前面的诉瓦，因為交換的肯定在left內(nèi)部去了。所以它原值就是在那力细，且經(jīng)過處理不用動睬澡，因此從left換到現(xiàn)在的cur之后，也是同樣的處理眠蚂，也不用動它煞聪，cur++拜拜嘞。
當cur遇到right逝慧，即到達2的邊界昔脯，則說明不需要處理了，結(jié)束笛臣。
題解代碼
class Solution {
public:
void sortColors(vector<int>& nums)
{
int left=0;
int right=nums.size()-1;
int cur=0;
while(cur<=right)
{
if(nums[cur]==0)//這個數(shù)字是0云稚，移動0區(qū)域內(nèi)，
{
swap(nums[cur],nums[left]);
//假如cur>left沈堡，left交換過來的值肯定已經(jīng)被處理過了静陈，但是處理時產(chǎn)生交換，原left指向的诞丽，一定是不用處理的嗎鲸拥？
//jeromememory：準確的說 cur 如果 與 p0 不是指向同一個索引，那 cur 指向的索引值如果發(fā)生交換僧免，那交換過來的一定是 1（原因是只有當遍歷過的節(jié)點有1刑赶，p0 和 cur 才不會同步），而 如果索引是 1 剛好也就不用有任何操作懂衩，所以可以直接++撞叨。
//假如cur==left==0金踪，沒啥好說的，下一個
//假如cur<left, 可能嗎谒所？cur++的機會 >= left++的機會
left++;
}
else if(nums[cur]==2)//這個數(shù)字是2热康，移到2區(qū)域內(nèi)
{
swap(nums[cur],nums[right]);
right--;
//交換過來的值，是右邊過來的劣领，cur沒處理過姐军，因此還需要對這個位置處理，--抵消++尖淘，位置不變
cur--;
}
cur++;
}
}
};
