什么是荷兰国旗问题?

来源:百度知道 编辑:UC知道 时间:2024/05/06 03:00:34
怎么解决?

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

/***荷兰国旗问题描述:把由数字0,1,2组成的
***序列经过1遍扫描,使所有的0位于最前,1位于
***中间,2位于最后**************************/

/*****本程序思想:采用双指针p和q,p指针向前遍历,
*****进行必要的交换;当遇到0时,q指针向后遍历,
*****把0插入到合适的位置*********************/

#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指针后移
}