题目描述：
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意: 不能使用代码库中的排序函数来解决这道题。
示例:
输入:
[2,0,2,1,1,0
]
输出:
[0,0,1,1,2,2
]
进阶：
一个直观的解决方案是使用计数排序的两趟扫描算法。 首先，迭代计算出0、1和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。 你能想出一个仅使用常数空间的一趟扫描算法吗？
解题思路：
因为数组中只包含 0 ， 1 ， 2 三个数字 1）、使用快速排序思路，首先将 2 排序到最右侧； 2）、使用快速排序思路，在 1）的前提下 将0排在最左侧；
代码实现（1）
class Solution {
public:
void sortColors(vector
<int>& nums
) {
int tmp
, i
= 0 , j
= nums
.size() - 1 ;
while (i
< j
) {
if (nums
[i
] < 2) {
i
++ ;
continue ;
}
if (nums
[j
] == 2) {
j
-- ;
continue ;
}
if (i
< j
) {
swap(nums
[i
] , nums
[j
]) ;
i
++ ;
j
-- ;
}
}
i
= 0 ;
while (i
< j
) {
if (nums
[i
] == 0) {
i
++ ;
continue ;
}
if (nums
[j
] > 0) {
j
-- ;
continue ;
}
if (i
< j
) {
swap(nums
[i
] , nums
[j
]) ;
i
++ ;
j
-- ;
}
}
}
};
解题思路：
1）、统计 0 ， 1， 2 的个数 ； 2）、按照0 ， 1， 2 的个数重新赋值nums数组；
代码实现（2）
class Solution {
public:
void sortColors(vector
<int>& nums
) {
int mapKV
[3] = {0 , 0 , 0} ;
int i
, j
, k
;
for (i
= 0 ; i
< nums
.size() ; i
++) {
mapKV
[nums
[i
]] ++ ;
}
k
= 0 ;
for (i
= 0 ; i
< 3 ; i
++)
{
j
= 0 ;
while (j
++ < mapKV
[i
]) nums
[k
++] = i
;
}
}
};
复杂度
时间复杂度：O（n） ； 空间复杂度：O（1） ；
