顏色分類
給定一個(gè)包含紅色、白色和藍(lán)色，一共 n 個(gè)元素的數(shù)組，原地**對它們進(jìn)行排序，使得相同顏色的元素相鄰，并按照紅色、白色、藍(lán)色順序排列。
此題中，我們使用整數(shù) 0、 1 和 2 分別表示紅色、白色和藍(lán)色。
示例:
輸入:** [2,0,2,1,1,0]
輸出: [0,0,1,1,2,2]</pre>
進(jìn)階：
- 一個(gè)直觀的解決方案是使用計(jì)數(shù)排序的兩趟掃描算法。
首先，迭代計(jì)算出0、1 和 2 元素的個(gè)數(shù)，然后按照0、1、2的排序，重寫當(dāng)前數(shù)組。 - 你能想出一個(gè)僅使用常數(shù)空間的一趟掃描算法嗎？
題目分析
- 相同元素相鄰，換句話說即分區(qū)存放，一個(gè)顏色一個(gè)區(qū)域，但因?yàn)檫@里顏色使用0 ，1，2表示，即對一個(gè)012的無序序列進(jìn)行排序，變成000...111....2222的順序。
正常排序算法都適用，只不過這里注意僅有三種可能的順序值，可以有特殊做法。
- 對于一個(gè)元素，我們將他分區(qū)時(shí)，肯定是插在區(qū)域的末尾，換句話說，我們只要保留每個(gè)區(qū)域的末尾下標(biāo)，插入的時(shí)候交換過去就可以了。
三個(gè)區(qū)域，其實(shí)我們只要確定了兩個(gè)區(qū)域即可確定第三個(gè)區(qū)域，因?yàn)?區(qū)域在最左邊，2區(qū)域在最右邊，方便程序定位，因此取0 2 的末尾指針保留下來。
- 確定了雙指針確定區(qū)域，那么怎么進(jìn)行遍歷處理呢？確定了分類移動(dòng)的位置，即cur遍歷每一位的數(shù)值，分類處理遇到0放左邊，遇到2放右邊，02放好了，則1的區(qū)域也放好了。
針對cur的分類處理：
是0，則和0的flag ，left交換值，同時(shí)left++。此時(shí)cur獲取的是之前的left交換過來的值。我們知道我們換過去的處理好了，那么這個(gè)換過來的還需要處理嗎？目前還不知道，先看2的情況的處理。
是2，則和2的flag，right交換，同時(shí)right--。同樣，此時(shí)cur獲取了交換過來的值，由于這個(gè)值必然是在cur右邊（因?yàn)樗窃璻ight，即cur的右邊界），則cur肯定沒有遍歷過這個(gè)值。
同時(shí)因?yàn)樗赾ur右邊，它也不可能是交換過去的，因?yàn)榻粨Q過去的值肯定都在0 2 區(qū)域里了。
因此這個(gè)值是野生的，所以cur在此停留，繼續(xù)處理這個(gè)交換過來的值。是1，因?yàn)槲覀儼? 2 排序好，1的區(qū)域自然就出來了，因此1直接不處理，過就好了
-
那么看看0的情況交換過來的值？首先這個(gè)值的位置關(guān)系，即原left是在cur左邊還是右邊呢？
只有當(dāng)left會在cur右邊時(shí)，left指向的才可能是cur沒處理過的，但此時(shí)cur在left內(nèi)部？那cur就是把一個(gè)0換到了外邊，把一個(gè)亂序的換進(jìn)了0的內(nèi)部，內(nèi)鬼毫無意義。
當(dāng)left在cur左邊時(shí)，即left指向的必定經(jīng)過了cur的洗禮，而且它必不是原來在后面被換到前面的，因?yàn)榻粨Q的肯定在left內(nèi)部去了。所以它原值就是在那，且經(jīng)過處理不用動(dòng)，因此從left換到現(xiàn)在的cur之后，也是同樣的處理，也不用動(dòng)它，cur++拜拜嘞。
當(dāng)cur遇到right，即到達(dá)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)//這個(gè)數(shù)字是0，移動(dòng)0區(qū)域內(nèi)，
{
swap(nums[cur],nums[left]);
//假如cur>left，left交換過來的值肯定已經(jīng)被處理過了，但是處理時(shí)產(chǎn)生交換，原left指向的，一定是不用處理的嗎？
//jeromememory：準(zhǔn)確的說 cur 如果 與 p0 不是指向同一個(gè)索引，那 cur 指向的索引值如果發(fā)生交換，那交換過來的一定是 1（原因是只有當(dāng)遍歷過的節(jié)點(diǎn)有1，p0 和 cur 才不會同步），而 如果索引是 1 剛好也就不用有任何操作，所以可以直接++。
//假如cur==left==0，沒啥好說的，下一個(gè)
//假如cur<left, 可能嗎？cur++的機(jī)會 >= left++的機(jī)會
left++;
}
else if(nums[cur]==2)//這個(gè)數(shù)字是2，移到2區(qū)域內(nèi)
{
swap(nums[cur],nums[right]);
right--;
//交換過來的值，是右邊過來的，cur沒處理過，因此還需要對這個(gè)位置處理，--抵消++，位置不變
cur--;
}
cur++;
}
}
};
