快排

$O(nlogn)$O(nlogn)

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

计数排序

$O(n)$O(n)

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int count[3]={0};
        for(const auto &it: nums) count[it]++;
        int idx = 0;
        for(int i = 0; i < count[0]; i++){
            nums[idx++] = 0;
        }
        for(int i = 0; i < count[1]; i++){
            nums[idx++] = 1;
        }
        for(int i = 0; i < count[2]; i++){
            nums[idx++] = 2;
        }
    }
};

三路快排（荷兰国旗问题）

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int  l = -1, r = nums.size();
        for(int i = 0; i < r; ){
            if(nums[i] == 1) i++;
            else if(nums[i] == 2){
                r--;
                swap(nums[r], nums[i]);
            }else{
                l++;
                swap(nums[l], nums[i]);
                i++;
            }
        }
    }
};