快速排序之荷兰国旗问题快速排序之荷兰国旗问题

描述
荷兰国旗有三横条块构成，自上到下的三条块颜色依次为红、白、蓝。现有若干由红、白、蓝三种颜色的条块序列，要将它们重新排列使所有相同颜色的条块在一起。本问题要求将所有红色的条块放最左边、所有白色的条块放中间、所有蓝色的条块放最右边。
文章图片

3种颜色（0，1，2）在一个数组里，每次只可交换一次，扫描一边后，三种颜色自然分开，应为颜色为：红，白，蓝，（荷兰国旗的颜色）所也叫荷兰国旗问题！
【快速排序之荷兰国旗问题】

数据如上面所示要求进行排序。时间复杂度O(n)
输出结果为：

分析：
这个问题就是一个排序问题。

需要把小于1的放在前面，1放在中间，2放在最后。，

第一种方法（并不是今天最终的方法，虽然是O(n)但是不是最好的）
统计法：
先跑一遍数组，统计出来有几个1，几个0，几个2；
最后在把数依次放进去。
代码如下：（注释很清楚大家一定能看懂）
#include
int main(void)
{
int a[]={1,0,2,0,1,1,2,0,2,1};
int length=sizeof(a)/sizeof(int); //求数组长度；
int i,l=0,m=0,n=0,x,y; //定义一堆变量
int flag=1; //给出flag
for(i=0; i {
if(a[i] {
l++; //统计0的个数
x=a[i]; //把0给x
}
else if(a[i]==flag)
m++; //统计一的个数
else
{
n++; //2的个数
y=a[i]; //把2给y
}
}
//下面就是装数的过程：
for(i=0; i a[i]=x;
for(i; i a[i]=flag;
for(i; i a[i]=y;
//输出
printf("输出结果是：\n");
for(i=0; i printf("%4d",a[i]);
return 0;

}
第二种方法：(就是今天的正餐了)
我们定义三个指针，一个头，一个尾，一个用来遍历；
i

leftright
i每找到一个小于flag的数，就和left交换，然后left++
i每找到一个大于flag的数，就和right交换，然后right--

大于的放后面，小于的放前面，等于的自然就放在中间了；
代码如下：（注释很清楚，有问题的地方我都详细注释了）
#include
//交换函数
void exchange(int &x,int &y)// 这里一定要传&x，&y，把他们的地址传来
{
int t;
t=x;
x=y;
y=t;
}
int main(void)
{
int a[]={1,0,2,0,1,1,2,0,2,1};
int length=sizeof(a)/sizeof(int); //求数组长度；
int flag=1;
int i=0,left=0,right=length-1; //放上左右指针
while(i {
if(a[i] {
exchange(a[i],a[left]); //交换
i++; //i跑
//因为从左边开始跑；
//交换之后的数一定是小于或者等于flag的
//要是大于就一定交换过了
left++; //左指针加一
}
else if(a[i]==flag)
i++; //直接跑
else
{
exchange(a[i],a[right]);
right--; //右指针减一
//这里为什么没有i++呢？
//因为你交换之后的数你还没有判断呢
//只有当它小于或者等于的时候才能++
}
}
//输出
printf("输出结果是：\n");
for(i=0; i printf("%4d",a[i]);
return 0;
}