近期更新：最后面有python版本
問(wèn)題：現(xiàn)有紅白藍(lán)三個(gè)不同顏色的小球恬口，亂序排列在一起校读，請(qǐng)重新排列這些小球，使得紅白藍(lán)三色的同顏色的球在一起祖能。這個(gè)問(wèn)題之所以叫荷蘭國(guó)旗問(wèn)題歉秫，是因?yàn)槲覀兛梢詫⒓t白藍(lán)三色小球想象成條狀物，有序排列后正好組成荷蘭國(guó)旗养铸。
解法1：
遍歷整個(gè)數(shù)組端考，算出紅白藍(lán)的數(shù)目各是多少，再遍歷一遍揭厚，填充對(duì)應(yīng)的顏色却特。時(shí)間復(fù)雜度為O（n）解法2：
想象有三個(gè)籃子，我們一次遍歷這些小球筛圆，然后進(jìn)行分揀裂明，只不過(guò)我們要不斷地?cái)U(kuò)充籃子的大小。下面程序中太援，i,k分別是紅色和藍(lán)色籃子界限闽晦。
typedef enum {red,white,blue} Color;
void HelanFlag(Color Buff[],UINT32 len)
{
//i之前放的是紅色的球，k之后放的是藍(lán)色的球提岔，j是遍歷的球
UINT32 i=0,j=0,k=len-1;
Color temp;
while(j<=k)
{
switch (Buff[j])
{
case red:
Buff[j] = Buff[i];
Buff[i] = red;
i++;
j++;
break;
case white:
j++;
break;
case blue:
Buff[j] = Buff[k];
Buff[k] = blue;
k--;
break;
}
}
}
注意上述的程序中藍(lán)色和紅色的處理略微有點(diǎn)不同仙蛉，因?yàn)榧t色是已經(jīng)遍歷過(guò)的了，i-1和j-1之間是沒(méi)有紅的了碱蒙，有的話之前就已經(jīng)放到<i的范圍以內(nèi)了荠瘪。
Paste_Image.png
Paste_Image.png
由以上的解題思路我們來(lái)看另外一個(gè)問(wèn)題：將一個(gè)數(shù)組的偶數(shù)放到前面夯巷，奇數(shù)放到后面。同樣的思路哀墓，就是用i和j作為界限趁餐，i一直向前行進(jìn)，遇到偶數(shù)直接前進(jìn)篮绰，遇到奇數(shù)將其放到j(luò)的位置后雷，然后將j位置的數(shù)丟給i位置，同時(shí)j前面吠各，j--臀突。
void EO(int Buff[],int len)
{
int i=0,j=len-1,Temp;
while (i<=j)
{
if(Buff[i]%2==0)
{
i++;
}
else
{
Temp = Buff[j];
Buff[j] = Buff[i];
Buff[i] = Temp;
j--;
}
}
}
# 荷蘭國(guó)旗
@print_result_after
def poland_flag(data):
zero_edge = 0
two_edge = len(data) - 1
walking_index = 0
while walking_index <= two_edge:
if data[walking_index] == 0:
data[walking_index] = data[zero_edge]
data[zero_edge] = 0
zero_edge += 1
walking_index += 1
elif data[walking_index] == 1:
walking_index += 1
else:
data[walking_index] = data[two_edge]
data[two_edge] = 2
two_edge -= 1
return data
