三色球和荷兰国旗问题分析 c语言代码详解

59 阅读 0 评论 39 点赞

我是靠谱客的博主整齐路人，最近开发中收集的这篇文章主要介绍三色球和荷兰国旗问题分析 c语言代码详解，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

此类问题，类似快排中partition过程。只是需要用到三个指针，一前begin，一中current，一后end，俩俩交换。

current遍历，整个数组序列，current指1 current++，
current指0，与begin交换，而后current++，begin++，
current指2，与end交换，而后，current不动，end--。

1）若遍历到的位置为0，则说明它一定属于前部，于是就和begin位置进行交换，然后current向前进，begin也向前进（表示前边的已经都排好了）。

2）若遍历到的位置为1，则说明它一定属于中部，根据总思路，中部的我们都不动，然后current向前进。

3）若遍历到的位置为2，则说明它一定属于后部，于是就和end位置进行交换，由于交换完毕后current指向的可能是属于前部的，若此时current前进则会导致该位置不能被交换到前部，所以此时current不前进。而同1），end向后退1。

为什么，第三步，current指2，与end交换之后，current不动了列，对的，正如algorithm__所说：current之所以与begin交换后，current++、begin++，是因为此无后顾之忧。而current与end交换后，current不动，end--，是因有后顾之忧。

读者可以试想，你最终的目的无非就是为了让0、1、2有序排列，试想，如果第三步，current与end交换之前，万一end之前指的是0，而current交换之后，current此刻指的是0了，此时，current能动么？不能动啊，指的是0，还得与begin交换列。

ok，说这么多，你可能不甚明了，直接引用下图，就一目了然了：

#include "stdafx.h"
#include "string.h"
#define N 20
#define BLUE 'b'
#define RED 'r'
#define WHITE 'w'
#define SWAP(x, y) {char temp;temp=color[x];color[x]=color[y];color[y]=temp;}

int main()
{
char color[N];
while(gets(color))
{
//三个数组下标的标兵来进行定位
int begin=0;
int current=0;
int end=strlen(color)-1;

for (int i=0;i<strlen(color);i++)
{
printf("%c",color[i]);
}
printf("n");
while(current<=end)
{
if (color[current]=='w')
{
current++;
}
else if (color[current]=='b')
{
SWAP(current,begin);
current++;
begin++;
}else
{
if (color[end]=='r'&&current<end)
{
end--;
}
SWAP(current,end);
end--;
}
}
for (int i=0;i<strlen(color);i++)
{
printf("%c",color[i]);
}
printf("n");
}
return 0;
}
#include <iostream>
 #include <stdlib.h>
 using namespace std;
 #define N 10
 void swap (int &var1, int &var2)
 {

int temp = var1;

var1 = var2;

var2 = temp;
 }
 void shuffle(int *array)
 {

int current = 0;

int end = N-1;

int begin = 0;

while( current<=end )

{

if( array[current] ==0 )

{

swap(array[current],array[begin]);

current++;

begin++;

}

else if( array[current] == 1 )

{

current++;

}

else{//When array[current] =2

swap(array[current],array[end]);

end--;

}

}
 }
 int main(int argc, char *argv[])
 {

int a[N];

int i;

for( i=0 ; i<N; i++ )

{

a[i] = rand()%3;

cout << a[i] << " ";

}

cout << endl;

shuffle(a);

for( int i=0 ; i<N ; i++ )

{

cout << a[i] << " ";

}

cout << endl;

return 0;
 }
详细查看 http://blog.csdn.net/dotneterbj/article/details/20039779