Leectode-颜色分类（中等）

题目描述

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

方法1：

用这道题默写了下三向切分的快排

class Solution {
public:
    void quicksort(vector<int>& nums,int left,int right){
        if(left>=right) return;
        srand(time(0));
        int pivot = rand() % (right - left + 1) + left;
        swap(nums[left],nums[pivot]);
        int v=nums[left];
        int lt=left,gt=right,i=left+1;
        while(i<=gt){
            if(nums[i]<v)
                swap(nums[i++],nums[lt++]);
            else if(nums[i]>v)
                swap(nums[i],nums[gt--]);
            else
                i++;
        }
        quicksort(nums,left,lt-1);
        quicksort(nums,gt+1,right);
    }
    void sortColors(vector<int>& nums) {
        quicksort(nums,0,nums.size()-1);
    }
};

方法2：

当然，最简单的还是直接sort

class Solution {
public:
    void sortColors(vector<int>& nums) {
        sort(nums.begin(),nums.end());
    }
};

方法3：

用单指针，先找到0，全通过交换放最前面，再找1，通过交换放在0后面，以此类推
为了提高通用性，把0,1,2,放数组了

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int flag[3]={0,1,2};
        int ptr=0;
        for(auto color:flag){
            for(int i=0;i<nums.size();i++){
                if(nums[i]==color)
                    swap(nums[i],nums[ptr++]);//ptr前都是排过顺序的
            }
    }
    }
};