三球排序问题_有三种颜色的小球,分别代表0(红色),1(白色),2(蓝色),打乱顺序,放在数组中,让后整

题目：

有三种颜色的球，白色（0表示），红色（1表示），蓝色（2表示）。
给出序列[2,1,0,1,2,0,0,1,2]，请按照白色，红色，蓝色给这个序列重新排序。
得到的结果为[0,0,0,1,1,1,2,2,2]。算法的时间复杂度为O(N)。

思路：

• 1 使用三个指针 begin, end, current。begin指向头部，end指向尾部，current指向头部。
• 2 指针的运动方式：
  
  • 2.1 当current指向0时，swap(current, begin), current++, begin++;
  • 2.2 当current指向1时，current++;
  • 2.3 当current指向2时，swap(current, end), end–;
• 3 整体思路就是通过current遍历整个数组，把0往前放，把2往后放。

#include <iostream>
#include <vector>
using namespace std;

1
2
3
4
5