首页 > 代码库 > July收集荷兰国旗问题之三路partition

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, 包含整个区间了


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