荷兰国旗问题:设有一个仅由红、白、兰这三种颜色的条块组成的条块序列。请编写一个时间复杂度为O(n)的算法,使得这些条块按红、白、兰的顺序排好,即排成荷兰国旗图案。
实现下列函数:
void HFlag(FlagList &f)
"荷兰国旗"的顺序表的类型FlagList定义如下:
#define red '0'
#define white '1'
#define blue '2'
typedef char ColorType;
typedef struct {
ColorType r[MAX_LENGTH+1];
intlength;
} FlagList;
其实描述起来很简单。给你一个数组,其中有0,1,2这三个数字。如何在一次遍历的前提下把这三种数字归类分组。比如
输入1 0 2 1 0 0 1 2 2 1 0 2,输出0 0 0 0 1 1 1 1 2 2 2 2。void HFlag(FlagList &f)
{
inti=0;
char *pRed =&f.r[0];
char *pBlue= &f.r[f.length-1];
while(i<f.length)
{
if( f.r[i] == red )
{
char cTemp = *pRed;
*pRed = f.r[i];
f.r[i] = cTemp;
pRed++;
}
if( f.r[i] == blue )
{
char cTemp = *pBlue;
*pBlue = f.r[i];
f.r[i] = cTemp;
pBlue--;
}
if( f.r[i] == white )
{
i++;
}
if( &f.r[i] > pBlue )
break;
}
}