75. Sort Colors

题目：

一个数组包含0，1，2，对他们进行排序

思路1： two-pass

大家都能想到的，对0 1 2进行计数，然后重新调整数组，共遍历两次

void sortColors(vector<int>& nums) { //two-pass
	int red = 0, white = 0, blue = 0;
	for_each(nums.begin(), nums.end(), [&](int &n) {
		switch (n)
		{
		case 0:++red; 
		case 1:++white; 
		case 2:++blue; break;
		};
	});
	auto it = nums.begin();
	for (; it < nums.begin() + red; ++it)
		*it = 0;
	for (; it < nums.begin() + white; ++it)
		*it = 1;
	for (; it < nums.begin() + blue; ++it)
		*it = 2;
}

思路2：one-pass

设置参数beg，end和i。
[0,beg)均是0，[beg,i)均是1，（end,sz)均是2。

使i从0遍历至end

• 若nums[i]==0, 与beg位置互换,然后i和beg进1
• 若nums[i]==1,i进1
• 若nums[i]==2,与end位置互换,此时end减1但是i不变,因为这个换过来的值是未知的,需要重新判定

void sortColors(vector<int>& nums) {
	int sz = nums.size();
	auto beg = 0, end = sz - 1, i = 0;
	
	while (i <= end) {
		if (nums[i] == 0)
			swap(nums[i++], nums[beg++]);
		else if (nums[i] == 2)
			swap(nums[i], nums[end--]);
		else
			++i;
	}
}