力扣题库——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交换，需要马上交换到前面！

得了。