【題目描述】
Given an array with?n?objects colored?red,white?or?blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.
Here, we will use the integers 0,1, and 2 to represent the color red, white, and blue respectively.
Notice：
You are not suppose to use the library's sort function for this problem.
You should do it in-place (sort numbers in the original array).
給定一個(gè)包含紅初家，白府瞄，藍(lán)且長(zhǎng)度為 n 的數(shù)組紧武，將數(shù)組元素進(jìn)行分類使相同顏色的元素相鄰症汹，并按照紅胖喳、白辟汰、藍(lán)的順序進(jìn)行排序烛恤。
我們可以使用整數(shù) 0，1 和 2 分別代表紅抵皱，白善榛，藍(lán)。
【注】：1呻畸、不能使用代碼庫(kù)中的排序函數(shù)來解決這個(gè)問題移盆。
2、排序需要在原數(shù)組中進(jìn)行擂错。
【題目鏈接】
www.lintcode.com/en/problem/sort-colors/
【題目解析】
由于只有三種顏色味滞，那么紅色必然在數(shù)組的左邊樱蛤，而藍(lán)色必然在數(shù)組的右邊钮呀。
那么我們只需要兩個(gè)變量記錄紅色所在區(qū)域的邊界[0, i]， 以及藍(lán)色所在區(qū)域的邊界[j,n-1]昨凡。那么白色所在的區(qū)域必然為(i,j).
怎樣得到紅藍(lán)兩色的邊界呢爽醋？
初始化： 紅色邊界i=0; 藍(lán)色邊界j=n-1;
為了加速運(yùn)算，可以預(yù)處理便脊，分別從左至右蚂四，從右至左，找到紅藍(lán)邊界，縮小搜索范圍遂赠。見代碼line[3,4]
假設(shè)當(dāng)前位置為k
（1） A[k] 為紅色久妆， 那么將該元素同紅色右邊界的后一個(gè)數(shù)互換。 A[k] ~ A[i++]
（2） A[k] 為藍(lán)色跷睦， 那么將該元素同藍(lán)色左邊界的前一個(gè)數(shù)互換筷弦。 A[k] ~ A[j--]
（3） A[k] 為白色， 那么當(dāng)前無需交換抑诸， k=k+1;
終止條件 k>j 此時(shí)不可能出現(xiàn)白色烂琴，可以退出了。
【參考答案】
