1.思路：

1.1思路1：

　　第一眼看到這樣的題目，會舉得非常簡單，隻需要兩次周遊數組就可以完成了。第一次周遊，掃描數組中的元素，每次遇到0則count0++，遇到1則count1++，遇到2則count2++，這樣一趟下來就能夠統計出數組中0,1,2的個數了。然後第二次周遊的時候，隻需要對數組進行重新指派就可以了，從頭開始指派count0個0，count1個1，count2個2。最終完成對數組的排序。

（計數排序做法）

1.2思路2：

　　既然是面試題，那麼肯定不會讓你這麼簡單就解決出來了的。面試官說，加入隻能進行一次周遊怎麼辦，然後你就不知道了。

　　這道題目如果隻能進行一次周遊，我們肯定會想到使用多指針。這種題目之前碰到過很多。類似折半查找需要設定兩個指針，不過這道題目卻需要三個指針，分别指向數組中0,1,2三個元素末尾。加入有排好序的數組{0,0,1,1,2,2}，那麼p0指向下标為1的那個0，p1指向下标為3的那個1，而p2則指向下标為5的那個2。

p0和p1從前往後掃描，p2從後往前掃描，

初始化時：

p0指向第一個非0元素，那麼arry[p0]=1||2

p1指向第一個非1元素，那麼arry[p1]=0||2

p2指向第一個非2元素，那麼arry[p2]=0||1

假如：

arry[p0]==2，arry[p2]==0，交換兩個元素

arry[p1]==2，arry[p2]==1，交換兩個元素

arry[p0]==1，arry[p1]==0，交換兩個元素

否則的話隻可能是p0，p1，p2指向的三個數各不相同，那麼進行如下指派

arry[p0]==0，arry[p1]==1，arry[p2]==2。

假如經過上述swap以後出現i>k的情況，将k=i。

原題

排序隻有1，2，3三個元素的數組，不能統計1，2，3的個數。

分析

這個題目，盡管也是排序，但卻不能使用快速排序的方法。隻有三個元素，如果時間複雜度仍舊是O(nlogn)，顯然不是最好的。那就可以使用線性的排序算法，例如計數排序，可是題目中要求，不能夠對1，2，3進行統計個數。那該如何處理呢？請大家看下面的方法，我們首先通過例子來說明：

2	1		3
p1	p2	p3

假設，我們有三個指針：p1、p2、p3.p1從左側開始，指向第一個非1的數字；p3從右側開始，指向第一個非3的數字。p2從p1開始周遊，如果是2，p2繼續周遊，直到p2遇到1或者3：

1. 如果遇到1，則和p1進行交換，然後p1向右，指向第一個非1的數字
2. 如果遇到3，則和p3進行交換，然後p3向左，指向第一個非3的數字

p1，p2

交換之後，p2繼續從p1開始，如果是2繼續周遊，如果是1或者3，重複上面的步驟，所得如下：

根據上面的方法繼續下去

p2在p3右側，算法結束。

總結一下上面的算法：

p1從左側開始，指向第一個非1的數字；p3從右側開始，指向第一個非3的數字。

1. p2從p1開始周遊，如果是2，p2繼續周遊，直到p2遇到1或者3

重複上面的步驟，直到p2在p3的右側結束。感覺思路有bug: [2,0,1] (不同)

void sort(int arr[],int len)     {         int i = 0;//頭指針指向0         int  j = len - 1;//尾指針指向2         int k = 0;         while (arr[i] == 0)             i++;         k = i + 1;         while (arr[j] == 2)             j--;         while (k < j)         {             if (arr[k] == 1)                 k++;             else if (arr[k] == 0)             {                 swap(arr[i], arr[k]);                 while (arr[i] == 0)                     i++;             }             else if (arr[k] == 2)             {                 swap(arr[k], arr[j]);                 while (arr[j] == 2)                     j--;             }         }     }      

最巧妙的思路

我們将1，2，3，替換為互質的2，3，5，得到如下：

			5

之後，乘起來得到的900.這900裡，除以2，有多少個2，就有多少個1；然後除以3，有多少個3，就有多少個3對應的2；然後除以5，有多少個5，就有多少個5對應的3。這是如何保證的呢？因為2，3，5是互質的。

如下：（分解質因數）

被除數	除數	商	餘數	排序結果
900		450
		225
		112		2嘗試結束，嘗試3
		75
		25
		8		3嘗試結束，嘗試5
				全部結束

最終結果為112233.上面的這種思路，實際上是計數的一種變種。

• 一個數組中隻有0,1,2三種元素，要求對這樣的數組進行排序

• 參考：第2章 排序 | | 第17節 三色排序練習題

C/C++基本文法學習

STL

C++ primer