题目说明

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

解法1

时间复杂度：O(n)

空间复杂度：O(1)

思路：使用计数排序法，先遍历一遍统计出各个颜色的个数，然后再遍历第二遍，按指定顺序赋值。

void sortColors(vector
    
     & nums) {    int count0 = 0,count1 = 0, count2 = 0;    for (int i = 0; i < nums.size(); i ++)    {        if (nums[i] == 0)            count0 ++;        else if (nums[i] == 1)            count1 ++;        else if (nums[i] == 2)            count2 ++;    }    for (int i = 0; i < nums.size(); i ++)    {        if (i < count0)            nums[i] = 0;        else if ( i < count0 + count1)            nums[i] = 1;        else            nums[i] = 2;    }}
    

解法2

时间复杂度：O(n)

空间复杂度：O(1)

思路：桶排序，建立数组来记录各个数值的个数，数组的下标即数值，数组中各个元素即相应的个数。第一次循环，将记录装入数组，第二次循环，将数组依次放入待排序数组之中。即完成排序。

比第一种解法更具拓展性。

void sortColors(vector
    
     & nums) {    int count[3] = {0};    for (int i = 0; i < nums.size(); i ++)    {        count[nums[i]] ++;    }    int j = 0;    for (int i = 0; i < nums.size();)    {        if (count[j]-- > 0)        {            nums[i++]  = j;        }        else            j ++;//下一个桶    }}