只含有1、2、3的数组排序

荷兰三色旗双指针解法 O(n)

cur 和 end 是左右一起遍历的指针， 时间O(n)；

先举出大量复杂测试用例一边想方案一边验证。

不要举 00 11 22 、 22 11 00 、 11 00 22 这类特点明显不够随机的用例。

用键盘随机按出：

231223321321

232123123

2312312321

23312123

2313123

思路：

设置三个标记指针，pos0，pos2，cur 令pos0从前往后遍历，指向第一个非0的位置，pos2从后往前遍历，指向第一个非2的位置 然后cur从pos0开始往后遍历： 遇到0就和pos0交换， while a[pos0] ==0 : pos0 = pos0 + 1 遇到1什么也不做; 遇到2就和pos2交换，pos2向前滑动到下一个非2的位置，交换后还要重新检查cur的值,如果cur是0, cur和pos0交换； 直到cur与pos2相遇。 一次遍历，复杂度是O(n)，因为每次操作都使得数组更为有序，不像快排需要重复比较，所以比应用快排的方法效率高一些。

一个数组中只有0,1,2三个元素，进行排序，要求时间复杂度为O(n). https://blog.csdn.net/fjqcyq2/article/details/48929825?locationNum=8