这道题目和分成两块的partition的扩展。比如有一堆0 1 2 数字组成的数组，要分成 00 00 11 1 1 222 2这样的顺序的。
利用lumoto版的partition能够非常好的解决，比hoare好多了。并且直接利用loop invariant，变成i j k三个指针，[low,i]=0 [i+1,j]=1, [j+1,k-1]=2, 里面假设新来2的话，直接k++，
假设是1的话，须要和a[j+1] swap, 同一时候j++, 假设0的话。须要先和a[i+1] swap i++, 然后和 a[j+1] swap j++, 因此算法例如以下：
void NertherlandFlags(int *a, int n)
{
int low=0,high=n-1;
int i=low-1,j=low-1;
for(int k=low;k<=high;k++)
{
if(a[k]==2) ;
else if(a[k]==1)
{
j++;
swap(a[j],a[k]);
}
else if(a[k]==0)
{
i++;
swap(a[i],a[k]);
j++;
swap(a[j],a[k]);
}
}
}
代码比較好写，感觉这都是一类题，
1.快排的partition。注意留一个pivot，算导是留最后一个，所以loop到high-1就停了，里面和pivot比。最后加一次swap把pivot放中间
loop invariant: [low,i] <pivot, [i+1, j-1]>pivot, =放那边都行。exit loop时 j=high, 最后把swap跳进来
2.奇偶排序，整个区间划分为左奇右偶。和%2=0 =1比。loop 到high，
loop invariant: [low,i] 奇, [i+1, j-1]偶, exit时 j=high+1, 包括整个区间了
3.荷兰国企问题，整个区间划分为0 1 2 (红 黄 蓝三块)， loop 到high,
loop invariant: [low,i] 0, [i+1, j] 1, [j+1, k-1] exit时 j=high+1, 包括整个区间了
抱歉大家，这道荷兰国旗代码有bug。我才知道的。后经过分析主要是前面仅仅有2 或者0 2时，假设来了0，后面swap(a[j],a[k]) 会多交换一次使得交换回去，所以假设仅仅有0的情况。事实上不须要交换，而swap(a[j],a[k]) swap(a[j],a[k])都是子交换，因此1次两次不影响。于是统一到一起就是没有1区间的时候，也即[i+1,j]区间空，依据性质最多相差1。因此是i==j的时候出错，所以此时少一次swap, 可是i++ j++须要的 保持ij同步
事实证明未经过OJ測试的代码非常难保证正确性。leetcode setcolor题 就是上面的挂了，于是经过多种组合条件分析发现bug。单独处理1 interval空的情况
void sortColors(int a[], int n) {
int i=-1,j=-1;
for(int k=0;k<=n-1;k++)
{
if(a[k]==0)
{
if(i==j)//before are 2 or 0 2, swap one is only, two will error, also 0 swap once is ok, so that is no 1 interval would only swap once
{
i++;
swap(a[i],a[k]);
j++;
}
else
{
i++;
swap(a[i],a[k]);
j++;
swap(a[j],a[k]);
}
}
else if(a[k]==1)
{
j++;
swap(a[j],a[k]);
}
}
}
附上July版本号，前面 0 1区间 最后面2区间 1 2 之间没处理的
void sortColors(int a[], int n) {
int begin=0,end=n-1,current=0;
while(current<=end)
{
if(a[current]==0)
swap(a[begin],a[current]),begin++, current++;
else if(a[current]==1)
current++;
else if(a[current]==2)
swap(a[current],a[end]),end--; //current not move
}
}
这样的不用考虑特殊情况。比方 仅仅有2 和仅仅有0 2的区间的情况，事实上也是单向扫描过来的，仅仅是调整了未处理部分和 0 1 2 区间的顺序而已，由于指针从current+1, 到end处理了。一个
指针扫描的，还是单向扫描好。事实上也不是Hoart版啦，所以自己不用管Hoard版，坚持Lumoto版就能够了，sumous_t大神似乎也是的。
似乎另一种改进第一个版本号的思路。就是不swap，而是覆盖，像优化partition一样的
附上July博客 https://github.com/bolpigo/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.07.md
sumous_t 大神代码： https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/code/python/2.8:%20%E8%8D%B7%E5%85%B0%E5%9B%BD%E6%97%97%E9%97%AE%E9%A2%98.py
再附上sumous_t大神帮我改动后AC的代码，膜拜下大神，还是女博士哦：）
void sortColors(int a[], int n) {
int low=0,high=n-1;
int i=low-1,j=low-1;
for(int k=low;k<=high;k++)
{
if(a[k]==2) ;
else if(a[k]==1)
{
j++;
swap(a[j],a[k]);
}
else if(a[k]==0)
{
i++;j++;swap(a[j],a[k]);swap(a[j],a[i]);
}
}
