Sort Colors

@(算法)[算法, Two Pointers, Sort, Array, Facebook]

这一题怎样用一句话描述？

将只包含0，1，2这三个数的数组排序

用到什么算法？什么数据结构？

计数排序/Two Pointers，数组

通过这题学到了什么？

这题通过计数排序很简单，时间复杂度也等于O(n)，但是能不能继续优化呢？还是可以的，算是这一题的出彩部分吧。代码可以参考九章的答案。由于只有三种数字，也就是说，排序后数组是分成左、中、右三块地，分别对应1，2，3。所以可以有以下思路：

就是用两个指向指针（一个指向当前未排序数组的最左边，一个指向当前未排序数组的最右边），和一个扫描指针，扫描指针用来将数组整个过一遍（但并不是每次循环指针都会向前）

当扫描指针碰到0时，就要与最左边的pl指向的元素交换，这样0就被放到了它应该出现的位置，而pl此时会向前移动，因为它知道自己前面的元素们已经有序了，i也会继续向前，因为它要扫描下一个元素了，pr不需要移动；
当扫描指针碰到1时，就不能与pl或者pr交换了，因为1在中间，不能放到两边去，所以i继续向前，其他指针不动；
当扫描指针碰到2时，就要与最右边的pr指向的元素交换，这样2就被放到了它应该出现的位置，而pl此时会向前移动（当然啦是向它的前方，也就是向数组中间靠拢），因为它也知道，自己身后的元素都已经有序了（都是2），但是i并不会继续向前，这里是因为交换过来的元素有可能还是2，i一走就没有谁可以发现这个2了。

那么问题来了，为什么碰到0的时候，i要继续向前，而碰到2的时候，i就不能继续向前了？如果碰到0，交换过来的还是0怎么办呢？完全没问题，不管交换过来0还是1（不可能是2，因为2早就换到后面了，所以当发生第一次i与pl的交换时，pl指向的绝不可能是2），pl都会兢兢业业地帮i记住（pl比i走得慢，pl总会又来到这个元素的位置），当i再次碰到0时又会和pl交换，总之不会漏掉。具体的证明可以作为本题的延伸思考。

可能(已经)遇到的BUG有？

i遇到0时不++，导致无限循环