July收集荷兰国旗问题之三路partition

这道题目和分成两块的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]);

        }  
    }

July收集荷兰国旗问题之三路partition

相关推荐