双指针

颜色分类，最令我头疼的一个双指针问题...

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意:
不能使用代码库中的排序函数来解决这道题。
示例:
输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]
进阶：
一个直观的解决方案是使用计数排序的两趟扫描算法。
首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
你能想出一个仅使用常数空间的一趟扫描算法吗？
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sort-colors
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

简单来说，就是将一个只包含0，1，2三种元素的数组，进行排序，但只能够进行一趟扫描。

为了深入理解这个问题，首先还是从简单的说起，也就是对于只包含0，1两种元素的数组进行排序。这个问题就直接对应着快速排序算法中的partion部分，这里直接给出对应的代码如下。思路也很简单，就是设置一个"指针"，来记录数组头部包含0元素的区间；再设置另外一个"指针"，在遍历数组的过程中，不断地将0元素移动到数组头部。

void sort_for_01array(vector<int> &nums){
    int p0 = 0, len = nums.size();
    for(int p1 = p0; p1 < len; ++p1){
        if(nums[p1]==0)
            swap(nums[p1], nums[p0++]); // [0, p0)区间的元素均为0
    }
}

而对于三种元素地划分，也继承了这样的思路，但却又因为一些限制因素，故不得不另外做出一定的改变。需要说明的是，问题的思路有多种，这里仅对自己的一个思路进行说明(争取能说明白...)

一个直接的思路是这样的：基于两种元素分类的思路，我们除了设置一个p0来记录0元素区间之外，再设置另一个变量p2来记录2元素区间，其中代表数组的元素个数。有了这两个区间之后，我们再设置一个变量p1来遍历数组，并在过程之中不断地将0移动到头部，将2移动到尾部。

乍一看好像没问题了，但真的是这样吗？

不妨举一个例子，[2,1,2]，根据上述的思路，整个遍历流程如下所示：

颜色分类.png

可以看出，该思路是不完善的，这里，我们就需要思考导致错误发生的关键点是哪里。其实就错在一个地方：当nums[p1]和nums[p2]交换的时候，我们不知道nums[p2]的值是哪一类！！！仔细思考一下，尾部的2元素区间为，因此nums[p2]并没有包含在尾部区间，那么，当nums[p2]被换到nums[p1]的位置的时候，我们就无法得到这个值到底是属于哪一类，相当于我们的p1指针对nums[p2]不起作用。

那么如何解决呢？再来一次！没错，就是将p1指针倒退一格，并重新对换到中间的nums[p2]进行判断，这样就完美地解决了问题了。

讲到这里，似乎还有一个问题没有想清楚。对于p2指针存在的问题，为什么p0指针就不需要考虑呢？因为头部的区间为，nums[p0]的类别我们也无法得知，将其换出去之后就不会有类似的bug了吗？

确实是没有bug的。因为p0<=p1永远成立(p1遍历过的元素包含了的所有元素)，因此只要p0<p1，那么p0指向的元素永远为1！因此不可能像p1和p2交换那样，将头部的0元素换到了后方。

OK，上面的问题就都解释清楚了，代码如下：

void sortColors(vector<int>& nums) {
    int len = nums.size();
    int p0 = 0, p2 = len-1;
    for(int p1 = p0; p1 <=p2; ++p1){
        if(nums[p1]==0)
            swap(nums[p1], nums[p0++]);
        else if(nums[p1]==2){
            swap(nums[p1], nums[p2--]);
            --p1; // 最关键的一步
        }
    }