荷兰旗问题(三色旗排序)

摘要：

荷兰旗问题是三色排序，即某一组数据，元素的值只能为a,b ,c。把这组数据按照a, b, c的顺序排序。

本文介绍了一种时间复杂度为O（n），空间复杂度O（1）的算法。

1. 问题描述

某盒子中有n个球，每个球的颜色可以是红、蓝、白，现在要求把球按照红、蓝、白的顺序摆放。这个问题叫做荷兰旗问题（荷兰旗由红、蓝、白三色组成）。

对问题的抽象：

一数列Data中含有n个元素：

Data = {A1, A2, A3, A4........, An}

Ai 属于{a, b, c}

要求：把Data按照a, b, c的顺序排列

Data = {a, a, ... b, b, b, ...., c,c,c...}

2. 问题分析

// aaa bbbbbb xxxx ccccc

// | | |

// p_b p_ch p_c
p_b ：第一个b的位置
p_c ：第一个c的位置

p_ch：当前处理的字符位置

具体过程如下：

绿色：要处理的字符

红色：交换字符

3. 算法实现

#include <stdio.h>
#include <stdlib.h>
#include <time.h>inline void Swap( char *ch1, char *ch2 )
{char tmp;tmp = *ch1;*ch1 = *ch2;*ch2 = tmp;
}void PartABC( char *data, int i_size)
{char *p_b = data;			//第一个b的位置 char *p_c = data+i_size-1;	//第一个c的位置 char *p_ch = data;			//当前处理的字符位置 //	aaa bbbbbb xxxx ccccc//      |      |    |     //     p_b    p_ch  p_c    while( p_ch != p_c )		 {if( *p_ch == 'b' )		//取第一个非b		{						          p_ch++;				    continue;}else if( *p_ch == 'a' )	//取到a 和 第一个b交换 {Swap( p_ch, p_b );p_ch++;p_b++;}else					//取到c 和 p_c前第一个非c交换					{while( *p_c == 'c' )	//ccc前第一个非c p_c--;Swap( p_ch, p_c );		//if( *p_ch == 'a' )		//第一个非c是a，在和第一个非b交换 {Swap(p_ch, p_b);p_b++;}p_ch++;}}//while
}int main(int argc, char *argv[])
{srand((unsigned)time(NULL));const int ki_size = 10;//char *cv_data = "cbbabbabca";char cv_data[ki_size+1];int i;for( i=0; i<ki_size; i++ ){cv_data[i] = rand()%3 + 'a';}cv_data[i] = '\0';printf("Data is : %s\n", cv_data);PartABC(cv_data, ki_size);printf("Sorted Data is : %s\n", cv_data);return 0;
}