给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意: 不能使用代码库中的排序函数来解决这道题。
示例:
输入: [2,0,2,1,1,0] 输出: [0,0,1,1,2,2] 进阶：
一个直观的解决方案是使用计数排序的两趟扫描算法。 首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。 你能想出一个仅使用常数空间的一趟扫描算法吗？
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/sort-colors 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路一：首先咱就把计数排序做一下，计数排序的主要思想是：
首先找到待排序数组nums中的最大值max_elem和最小值min_elem；
再计算出d = max_elem - min_elem，构造临时数组temp，大小为d+1，因为索引从0开始；
依次计算出待排序数组元素在数组中的出现次数，并记录在temp数组中，并对temp数组从第二项开始与前项求和，这样temp[nums[i] - min_elem] - 1就是该元素在待排序数组中应该存放的位置。
反向填充结果数组res。为了保证稳定性，每一个元素放在其应该放置的位置之后，应该将其在temp中的值减一，这样是为了保证重复元素可以放在正确的位置。
举个栗子：
例如：待排序数组为：A{2,5,3,0,2,3,0,3} 那么最大值max_elem = 5; 最小值为min_elem = 0; 所以d = 5 - 0 = 5; 所以temp数组最后的结果是：temp{2,2,4,7,7,8} 那么3这个元素应该放在temp[nums[7] - 0] - 1 = 6这个索引对应的位置上。即位置7 上。
代码实现：
class Solution { public: void sortColors(vector<int>& nums) { int n = nums.size(); if(n == 0) return; int max_elem = *max_element(nums.begin(),nums.end()); int min_elem = *min_element(nums.begin(),nums.end()); int d = max_elem - min_elem; vector<int> temp(d + 1,0); vector<int> res(nums.size(),0); for(int i = 0;i < nums.size();++i) { ++temp[nums[i]- min_elem]; } //计算累加和 for(int j = 1;j <= d;++j) { temp[j] = temp[j] + temp[j-1]; } // 反向填充数组，从统计数组找到正确的位置，输出到结果数组 for(int k = n - 1;k >= 0;k--) { res[temp[nums[k] - min_elem] - 1] = nums[k]; --temp[nums[k] - min_elem];//使重复元素能够往前放 } nums = res; } };思路二：三指针法，维护一个left指针和一个right指针，其中left为元素0的右边界，指针right为元素2的左边界，那么我们遍历到一个0，就往左边界添加，同时更新左边界，遍历到一个2，就往右边界添加，同时更新有边界，这里需要注意的是，如果我们遍历到的是2，那么暂时不需要将cur继续往后递增，因为换回来的元素不知道是0还是1，如果是0的话还需要继续与左边界交换，的如果是1的话还要重新换出去。
代码实现：
class Solution { public: void sortColors(vector<int>& nums) { int n = nums.size(); if(n == 0) return; //三指针法 int left = 0;//0的右边界（哨兵） int right = n - 1 ;//2的左边界（哨兵） int cur = 0; while(cur <=right)//我们不能遍历超过right指针 { if(nums[cur] == 0) { swap(nums[cur++],nums[left++]); } else if(nums[cur] == 2) { swap(nums[cur],nums[right--]);//注意这里的cur不需要移动因为我们还需要检查换回来的值是0还是1 } else { ++cur; } } return; } };