第一眼看到这样的题目，会举得非常简单，只需要两次遍历数组就可以完成了。第一次遍历，扫描数组中的元素，每次遇到0则count0++，遇到1则count1++，遇到2则count2++，这样一趟下来就能够统计出数组中0,1,2的个数了。然后第二次遍历的时候，只需要对数组进行重新赋值就可以了，从头开始赋值count0个0，count1个1，count2个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。（PS：2012-10-5）
#include<iostream>#include<stdlib.h>using namespace std;void PrintArry(int arry[],int len){ for(int i=0;i<len;i++) cout<<arry[i]<<" "; cout<<endl;}void swap(int arry[],int i,int j){ int temp=arry[i]; arry[i]=arry[j]; arry[j]=temp;}void sort(int arry[],int len){ int i= 0;//头指针指向0 int j = len - 1;//尾指针指向2 int k = 0;//中间指针指向1 while(i <= j && k <= j && i <= k) { //i指向第一个非0值 while(arry[i] == 0){ i++; } //k指向第一个非1值 while(arry[k] == 1){ k++; } //j指向第一个非2值 while(arry[j] == 2){ j--; } if(i <= j && arry[j] == 0 && arry[i] == 2){ swap(arry,i,j); i++; j--; } else if(k <= j && arry[k] == 2 && arry[j] == 1){ swap(arry,k,j); k++; j--; } else if(i <= k && arry[k] == 0 && arry[i] == 1){ swap(arry,k,i); i++; k++; } else if(i < k && k < j){ arry[i] = 0; arry[k] = 1; arry[j] = 2; i++; k++; j--; } if(i>k) { k=i; } } }void main(){ int arry[]={1,0,2,2,0,1,0,1}; int len=sizeof(arry)/sizeof(int); PrintArry(arry,len); sort(arry,len); PrintArry(arry,len); system("pause");}
转自：http://www.cnblogs.com/xwdreamer/archive/2012/05/17/2506042.html
排序只有1，2，3三个元素的数组，不能统计1，2，3的个数。
这个题目，尽管也是排序，但却不能使用快速排序的方法。只有三个元素，如果时间复杂度仍旧是O(nlogn)，显然不是最好的。那就可以使用线性的排序算法，例如计数排序，可是题目中要求，不能够对1，2，3进行统计个数。那该如何处理呢？请大家看下面的方法，我们首先通过例子来说明：
| 2 | 1 | 1 | 3 | 3 | 2 |
| p1 | p2 | p3 |
假设，我们有三个指针：p1、p2、p3.p1从左侧开始，指向第一个非1的数字；p3从右侧开始，指向第一个非3的数字。p2从p1开始遍历，如果是2，p2继续遍历，直到p2遇到1或者3：
如果遇到1，则和p1进行交换，然后p1向右，指向第一个非1的数字
如果遇到3，则和p3进行交换，然后p3向左，指向第一个非3的数字
| 1 | 2 | 1 | 3 | 3 | 2 |
| p1，p2 | p3 |
交换之后，p2继续从p1开始，如果是2继续遍历，如果是1或者3，重复上面的步骤，所得如下：
| 1 | 1 | 2 | 3 | 3 | 2 |
| p1，p2 | p3 |
根据上面的方法继续下去
| 1 | 1 | 2 | 2 | 3 | 3 |
| p1 | p3 | p2 |
p2在p3右侧，算法结束。
总结一下上面的算法：
p1从左侧开始，指向第一个非1的数字；p3从右侧开始，指向第一个非3的数字。
p2从p1开始遍历，如果是2，p2继续遍历，直到p2遇到1或者3
如果遇到1，则和p1进行交换，然后p1向右，指向第一个非1的数字
如果遇到3，则和p3进行交换，然后p3向左，指向第一个非3的数字
重复上面的步骤，直到p2在p3的右侧结束。
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--; } }}
上面的思路，是针对三个数的，如果有更多的数，怎么处理呢？比如，4个，5个等等。下面根据快速的排序的启发，介绍一种算法，尽管在处理三个数的时候，比较次数会多些，但，具有很好的通用性。
思路来自快排的划分部分，快排的划分部分：给定pivot，然后将数据划分为<=pivot和>pivot两部分。这样，三个数字时，需要两次划分：
第一次，用1作为pivot,划分1到最左边；
第二次，用2作为pivot，划分2到左边，则得到整体的排序。
我们将1，2，3，替换为互质的2，3，5，得到如下：
| 2 | 1 | 1 | 3 | 3 | 2 |
| 3 | 2 | 2 | 5 | 5 | 3 |
之后，乘起来得到的900.这900里，除以2，有多少个2，就有多少个1；然后除以3，有多少个3，就有多少个3对应的2；然后除以5，有多少个5，就有多少个5对应的3。这是如何保证的呢？因为2，3，5是互质的。
如下：（分解质因数）
| 被除数 | 除数 | 商 | 余数 | 排序结果 |
| 900 | 2 | 450 | 0 | 1 |
| 450 | 2 | 225 | 0 | 1 |
| 225 | 2 | 112 | 1 | 2尝试结束，尝试3 |
| 225 | 3 | 75 | 0 | 2 |
| 75 | 3 | 25 | 0 | 2 |
| 25 | 3 | 8 | 1 | 3尝试结束，尝试5 |
| 25 | 5 | 5 | 0 | 3 |
| 5 | 5 | 1 | 0 | 3 |
| 1 | 5 | 1 | 1 | 全部结束 |
最终结果为112233.上面的这种思路，实际上是计数的一种变种。没有直接的技术，那自然就是可以的。
【分析完毕】
联系客服
