荷兰国旗问题：设有一个仅有红、白、蓝三种颜色的条块组成的条块序列，用一个时间复杂度为O(n)的算法，使得 这些条块按红、白、蓝的顺序排列，即排成荷兰国旗图案。

今天又做了一次数据结构考过的荷兰国旗问题，设红白蓝用（2，1，0）表示，蜕化为一道排序题。开始想法是双指针遍历，从头开始扫描，遇到1交换到数组尾，遇到0继续，遇到2则放在数组头，这样一次for循环结束就排好了，时间复杂度O(n)，空间1个（用于交换）。

然后突然想到了一个算法，for循环一次，记录2和1的个数，3个for循环从左到右给数组赋2，1，0三个值，共用时2n次，时间复杂度也是O(n)，空间0个。

最后，看看题目，叫荷兰国旗问题，荷兰国旗总不会是3种颜色不对称的吧，每种颜色n/3个，还是3个for循环赋值，时空与上面一样。
#include<iostream>
using namespace std;
void sortHL(int* a,int n)
{
         int j=0,k=0,i;//j记录有红色块数，k记录蓝色块数
for(i=0;i<n;i++)
{

      if(a[i]==1)//蓝色
   j++;
             if(a[i]==2)//红色
   k++;

}
for(i=0;i<=k-1;i++)//前k块为红色
   a[i]=2;
for(i=k;i<=n-j;i++)//中间是白色
   a[i]=0;
         for(i=n-j;i<=n-1;i++)//后j块是蓝色
   a[i]=1;
}
int main()
{
   int a[]={0,1,0,2,2,0,1,2,1};//原数组
   int n=sizeof(a)/sizeof(int);//数组长度
   for(int i=0;i<n;i++)
cout<<a[i];
   cout<<endl;
   sortHL(a,n);
   for(i=0;i<n;i++)
cout<<a[i];//输出排好的国旗
   cout<<endl;
   return 0;
}

3种颜色（0，1，2）在一个数组里，每次只可交换一次，扫描一边后，三种颜色自然分开，应为颜色为：红，白，蓝，（荷兰国旗的颜色）所也叫荷兰国旗问题！ 
设有一个仅有红、白、蓝三种颜色的条块组成的条块序列，用一个时间复杂度为O(n)的算法，使得 
这些条块按红、白、蓝的顺序排列，即排成荷兰国旗图案。 

 

 

#include <iostream> 
using namespace std; 

const int N = 20; 
int iarray[N] = { 0, 2, 1, 2, 0, 1, 0, 2, 2, 1, 
0, 1, 2, 1, 1, 0, 0, 1, 1, 2}; //待处理的数组 

 
void swap_ab ( int *p , int *q ) 
{ 
int tmp = *p; 
*p = *q; 
*q = tmp; 
} 

 
void process ( int a[], int n ) 
{ 
int *p, *q; 
p = q = a; 
//p向前遍历，直到便利完毕 
while ( p != a+n-1 ) 
{ 
if ( *(p+1) < *p ) 
{ 
q = p+1; 
while ( *q < *(q-1) ) 
{ 
swap_ab ( q, q-1 ); 
--q; //q指针后移 
} 
} 
//如果不需要交换，p指针直接前移 
++p; 
} 
} 

 
void print ( int a[], int n ) 
{ 
for (int i=0; i< n; ++i ) 
{ 
cout << a[i] <<" "; 
} 
cout << endl; 
} 

int main() 
{ 
cout << "处理前的数组序列: " <<endl; 
print ( iarray, N ); 
cout << "处理后的数组序列: " <<endl; 
process ( iarray, N ); 
print ( iarray, N ); 
return 0; 
}