题海拾贝：力扣 75.颜色分类

1、题目 

2、题解 

        我们甚至都不用看题，直接看他那个示例，这不就是升序排序吗？那我们直接用c++自带的sort就行了。但是我们再看看题，人家不让用sort，那咱们自己写个冒泡排序不就完了吗？

代码（一）：

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int i=0;
        int j=0;
        for(i=0;i < nums.size()-1;i++)
        {
            for(j=0;j<nums.size()-i-1;j++)
            {
                if(nums[j]>nums[j+1])
                {int temp;
                temp=nums[j];
                nums[j]=nums[j+1];
                nums[j+1]=temp;}
            }

        }

    }
};

        没错，这个题就这么简单，通过了。但是咱们还是继续优化一下，毕竟他的复杂度O（n^2）还是不太好看。 

        我们现在运用一下上一篇的思想，也就是分块数组。这个题出现的数组只有0 1 2，那咱们创建三个变量充当指针，从头遍历数组，如果大于1那就往后放（和后面的交换位置），如果小于1那就往前放。

代码（二）：

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int i=0;//遍历数组
        int j=0;
        int n=nums.size();
        while(i<n)
        {
            int temp;
            if(nums[i]>1)
            {
                temp=nums[i];
                nums[i]=nums[--n];
                nums[n]=temp;//已经减小一次了就别再减了
                //注意这里不要让i++，因为咱们不知道之前在a[n]那放着的值的大小
            }
            else if(nums[i]==1)
            {
                i++;
            }
            else
            {
                temp=nums[i];
                nums[i]=nums[j];
                nums[j]=temp;
                i++;j++;
            }
        }

    }
};

        注意我们写这个n的时候，我们要保证他先减小再交换。因为如果说我们有个位置还没交换的话，就让n先过去了，到最后i++等于n的时候有可能会出现Bug,由于我们这时候n这个位置还没有被判断过，但是i和n相等就退出循环了，所以部分测试案例过不了。

        另外就是以上的交换操作我们可以使用c++自带的swap函数，直接替换掉就可以了。

        好了，今天的内容就分享到这，我们下期再见！