class Solution {
public:
	void holandFlag(int a[], int n) {
		int i = -1;//令i为数组中第一个元素之前的一个元素
		int j = n;//令j为数组中最后一个元素之后的一个元素
		int index = 0;//index为数组中第一个元素的下标，用它来遍历数组
		while (index<j)//循环结束条件，此方法不用遍历全部的数组元素，当index和j相遇说明整个数组已经排列好
		{
//如果index下标处的值为0，则先将++i，然后交换，交换完成之后将index++
			if (a[index] == 0) {
				swap(a[++i], a[index]);
				index++;
			}
//如果index下标处的值为2，则先将--j，然后交换，交换完成之后index不++，因为无法保证后边的数，是否符合我们的排序要求
			else if (a[index] == 2)
			{
				swap(a[--j], a[index]);
			}
//如果index下标处的值为1，将index++
			else
			{
				index++;
			}
		}
	}
//打印数组
	void print(int a[],int n) {
		for (int i = 0; i < n; i++) {
			cout << a[i] << "  ";
		}
		cout << endl;
	}
};
int main() {
	Solution s;
	int a[] = { 1,2,0,2,1,1,0,0,2,1 };
	s.holandFlag(a, 10);
	s.print(a, 10);
	return 0;
}