待补充

题目：一个数组中只有0,1,2三种元素，要求对这样的数组进行排序。

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。（PS：2012-10-5）

2.代码示例

View Code

 本文转自xwdreamer博客园博客，原文链接http://www.cnblogs.com/xwdreamer/archive/2012/05/17/2506042.html，如需转载请自行联系原作者