###75. Sort Colors
题目: https://leetcode.com/problems/sort-colors/
难度:
Medium
思路:
这个问题是 Dutch National Flag Problem， 荷兰旗问题 https://en.wikipedia.org/wiki/Dutch_national_flag_problem
思路其实是类似partition的，比x小的放左边，比x大的放右边。
这里是用三个指针，begin, cur, end，cur需要遍历整个数组
- cur 指向0，交换begin与cur， begin++,cur++
- cur 指向1，不做任何交换，cur++
- cur 指向2，交换end与cur，end--
之所以cur指向2，交换之后不前进是因为我们不知道end此时指向的元素是几，如果交换过来的是0或者1，那么明显我们需要做进一步的处理，所以最终判断条件是end =< cur应该就结束了
这样的three-way-partition也只是3-way好用吧？如果有4个数，那么这样则是无效的，或者如果是4-way，那么可以转换成3-way+2-way
class Solution(object):
def sortColors(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
begin,cur,end = 0,0,len(nums) - 1
while cur <= end:
if nums[cur] == 0:
nums[begin],nums[cur] = nums[cur],nums[begin]
cur += 1
begin += 1
elif nums[cur] == 1:
cur += 1
else: # nums[cur] == 2
nums[cur],nums[end] = nums[end],nums[cur]
end -=1