一、问题
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意:
不能使用代码库中的排序函数来解决这道题。
示例:
输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sort-colors
二、解决
思路一：计数排序：扫描一遍数组统计 0 1 2 三个元素的个数，然后再依次放回数组。适用于元素个数有限的情况下。
代码：
1 class Solution { 2 public: 3 void sortColors(vector<int>& nums) { 4 int count[3]={0}; // 声明个数组用于存放0 1 2三个元素的频率 5 for(int i=0;i<nums.size();i++){ 6 assert(nums[i]>=0&&nums[i]<=2); 7 //假如i=0，则相应count数组0索引的元素加1；i=1,则相应count数组1索引的元素加1 8 count[nums[i]]++; 9 } 10 //for循环结束后 count数组各索引值为0 1 2三个元素在nums数组中的个数。 11 12 int index=0; 13 //先放0这个元素，0共有count[0]个所以循环count[0]次 14 for(int i=0;i<count[0];i++) 15 nums[index++]=0; //将index索引依次放置为0。 16 for(int i=0;i<count[1];i++) 17 nums[index++]=1; 18 for(int i=0;i<count[2];i++) 19 nums[index++]=2; 20 } 21 };
时间复杂度O(n) 空间复杂度为O(k) k=3因为k为常数所以为O(1)。
思路二：三路快速排序，选取一个切分点v（有的书翻译为枢纽元），则排好序后整个数组分为小于v；等于v；大于v三段。
设置三个索引：zero和two 以及移动索引i。索引位置如下图
当 i 遍历到e这个元素时
如果e=1，则将e并入1中，然后i后移一位即可。
如果e=2，则将two索引前面的元素（two索引前面的元素值未知）与e交换位置，此时i不动，然后two向前移动一位即可。
如果e=1，则将e元素与zero索引后的元素交换位置（zero索引后的元素一定为1），所以交换后i向后移一位，zero也向后移一位。
最终排序完成如下图
代码：
1 class Solution { 2 public: 3 void sortColors(vector<int>& nums) { 4 int zero=-1; //设置为-1 表示对于闭区间[0...zero]==0为无效区间。 5 int two=nums.size(); // [two...n-1]==2 6 7 for(int i=0;i<two;){ //不需写i++因为有的情况i不需加加。 8 if(nums[i]==1){ // 如果e为1 9 i++; // 则只需i索引向后移动一位即可。 10 } 11 else if(nums[i]==2){ 12 two--; // 首先two-- 表示此时索引two指向之前two索引的前一个元素。 13 // 将two索引前一个元素与此时i索引指向的元素（e）交换位置 14 swap(nums[i],nums[two]); 15 } 16 else{ 17 assert(nums[i]==0); 18 zero++; 19 swap(nums[zero],nums[i]); 20 i++; 21 } 22 } 23 24 } 25 };
代码参考：https://github.com/liuyubobobo/Play-Leetcode