力扣题库——75.颜色分类

这道题采用三路快速排序，快速排序思路看这里快速排序。将数列分为三组：小于基准、等于基准、大于基准。和快排一样，对左右递归进行快速排序。

先将题目简化，如果只有数字0和1，扫描一遍数组，遇到数字1不用管，如果遇到第几个数字0，就和第几个数进行交换。代码如下：

int zero=0;
for(int i=0;i<nums.size()-1;i++)
{if(nums[i]==0){swap(nums[i],num[zero++]);}
}

再看另一种情况，只有数字1和2，采用相同的思路：

int two=nums.size()-1;
for(int i=0;i<=two;i++)
{while(nums[i]==2&&i<=two){swap(nums[i],nums[two--]);}
}

最后进行合并：

 int zero=0,two=nums.size()-1;for(int i=0;i<=two;i++){while(nums[i]==2&&i<=two){swap(nums[i],nums[two--]);}if(nums[i]==0){swap(nums[i],nums[zero++]);}}}

注：while语句要放到if语句前面，因为交换时可能会把0交换，需要马上交换到前面！

得了。