leetcode 75 Sort Colors 计数排序，三路快排

解法一：计数排序：统计0，1，2 的个数

时间复杂度：O(n)

空间复杂度：O(k)    k为元素的取值范围, 此题为O(1)

class Solution {

public:

    void sortColors(vector<int>& nums) {

        int count[] = {};  //存放0，1，2三个元素的频率

        for(int i=;i<nums.size();i++){

            assert(nums[i] >= && nums[i]<=);  //若不符合条件则报错

            count[nums[i]] ++;

        }

        int index = ;

        for(int i=;i<count[];i++)

            nums[index++] = ;

        for(int i=;i<count[];i++)

            nums[index++] = ;

        for(int i=;i<count[];i++)

            nums[index++] = ;

    }

};

解法二：三路快排

时间复杂度：O(n)

空间复杂度：O(1)

只遍历了一遍

class Solution {

public:

    void sortColors(vector<int>& nums) {

        int zero = -; //nums[0...zero] == 0 , 即设置初始状态为无效的数组

        int two = nums.size();  //nums[two...n-1] ==2, 初始化two==n

        for(int i=;i<two;){

            //有一部分i不需要++

            if(nums[i] == )

                i++;

            else if(nums[i] ==){

                two -- ; //two移位到前一位，即还没有处理的元素上

                //将two前的还未排序的元素与2交换位置

                swap(nums[i],nums[two]);

            }

            else{

                //nums[i] == 0

                assert(nums[i] ==);

                zero ++ ;

                //zero++后指向的是1，相当于将1和0交换位置，所以i++

                swap(nums[zero],nums[i]);

                i++;

            }

        }

    }

};